We study the problem of designing a data structure that reports the positions of the distinct @math -majorities within any range of an array @math , without storing @math . A @math -majority in a range @math , for @math , is an element that occurs more than @math times in @math . We show that @math bits are necessary for any data structure able just to count the number of distinct @math -majorities in any range. Then, we design a structure using @math bits that returns one position of each @math -majority of @math in @math time, on a RAM machine with word size @math (it can output any further position where each @math -majority occurs in @math additional time). Finally, we show how to remove a @math factor from the time by adding @math bits of space to the structure.
The time can be improved to @math on a RAM machine of @math bits by sampling, for each increasing interval of @math of length more than @math , one value out of @math . Predecessor data structures are built on the samples of each interval, taking at most @math bits. Then we first run a predecessor query on @math , which takes time @math @cite_21 , and finish with an @math -time binary search between the resulting samples.
@cite_21
2949195484
We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an explicit problem which breaks this communication complexity barrier. In addition, our bounds give the first separation between polynomial and near linear space. Such a separation is inherently impossible by communication complexity. Using our lower bound technique and new upper bound constructions, we obtain tight bounds for searching predecessors among a static set of integers. Given a set Y of n integers of l bits each, the goal is to efficiently find predecessor(x) = max y in Y | y <= x , by representing Y on a RAM using space S. In external memory, it follows that the optimal strategy is to use either standard B-trees, or a RAM algorithm ignoring the larger block size. In the important case of l = c*lg n, for c>1 (i.e. polynomial universes), and near linear space (such as S = n*poly(lg n)), the optimal search time is Theta(lg l). Thus, our lower bound implies the surprising conclusion that van Emde Boas' classic data structure from [FOCS'75] is optimal in this case. Note that for space n^ 1+eps , a running time of O(lg l lglg l) was given by Beame and Fich [STOC'99].