We consider the problem of performing predecessor searches in a bounded universe while achieving query times that depend on the distribution of queries. We obtain several data structures with various properties: in particular, we give data structures that achieve expected query times logarithmic in the entropy of the distribution of queries but with space bounded in terms of universe size, as well as data structures that use only linear space but with query times that are higher (but still sublinear) functions of the entropy. For these structures, the distribution is assumed to be known. We also consider individual query times on universe elements with general weights, as well as the case when the distribution is not known in advance.
We obtain matching upper and lower bounds for the amount of time to find the predecessor of a given element among the elements of a fixed compactly stored set. Our algorithms are for the unit-cost word RAM with multiplication and are extended to give dynamic algorithms. The lower bounds are proved for a large class of problems, including both static and dynamic predecessor problems, in a much stronger communication game model, but they apply to the cell probe and RAM models. 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 ∈ Y | y ≤ x). For this purpose, we represent Y on a RAM with word length b using S ≥ nl bits of space. Defining a = lg S n, we show that the optimal search time is, up to constant factors: min(logbn, lgl-lg n n, lg(l a) lg(a lg n * lg l a), lg (l a) lg (lg (l a) lg (lg n a)).In external memory (b > l), 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 b = l = γ lg n, for γ > 1 (i.e. polynomial universes), and near linear space (such as S = n • lgO(1) n), the optimal search time is Θ(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 n1+e, a running time of O(lg l lg lg l) was given by Beame and Fich [STOC'99].