Abstract

In the range α-majority query problem, we are given a sequence S[1 … n] and a fixed threshold α∈ (0 , 1) , and are asked to preprocess S such that, given a query range [i… j] , we can efficiently report the symbols that occur more than α(j- i+ 1) times in S[i… j] , which are called the range α-majorities. In this article we describe the first compressed dynamic data structure for range α-majority queries. It represents S in compressed space—nHk+ o(nlg σ) bits for any k= o(lg σn) , where σ is the alphabet size and Hk≤ H≤ lg σ is the kth order empirical entropy of S—and answers queries in O(lgnαlglgn) time while supporting insertions and deletions in S in O(lgnα) amortized time. We then show how to modify our data structure to receive some β≥ α at query time and report the range β-majorities in O(lgnβlglgn) time, without increasing the asymptotic space or update-time bounds. The best previous dynamic solution has the same query and update times as ours, but it occupies O(n) words and cannot take advantage of being given a larger threshold β at query time. We also design the first dynamic data structure for range α-minority—i.e., find a non-α-majority that occurs in a range—and obtain space and time bounds similar to those for α-majorities. We extend the structure to find Θ(1 / α) α-minorities at the same space and time cost. By giving up updates, we obtain static data structures with query time O((1 / α) lg lg wσ) for both problems, on a RAM with word size w= Ω(lg n) bits, without increasing our space bound. Static alternatives reach time O(1 / α) , but they compress S only to zeroth order entropy (H) or they only handle small values of α, that is, lg (1 / α) = o(lg σ).