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 present a new finger search tree with O(loglogd) expected search time in the Random Access Machine (RAM) model of computation for a large class of input distributions. The parameter d represents the number of elements (distance) between the search element and an element pointed to by a finger, in a finger search tree that stores n elements. Our data structure improves upon a previous result by Andersson and Mattsson that exhibits expected O(loglogn) search time by incorporating the distance d into the search time complexity, and thus removing the dependence on n. We are also able to show that the search time is O(loglogd+ϕ(n)) with high probability, where ϕ(n) is any slowly growing function of n. For the need of the analysis we model the updates by a “balls and bins” combinatorial game that is interesting in its own right as it involves insertions and deletions of balls according to an unknown distribution. Given a bounded universe 0 , 1 , ? , U - 1 , we show how to perform predecessor searches in O ( log log Δ ) expected time, where Δ is the difference between the element being searched for and its predecessor in the structure, while supporting updates in O ( log log Δ ) expected amortized time, as well. This unifies the results of traditional bounded universe structures (which support predecessor searches in O ( log log U ) time) and hashing (which supports membership queries in O ( 1 ) time). We also show how these results can be applied to approximate nearest neighbour queries and range searching. We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an optimal bound of O(slog n log log n) for searching and updating a dynamic set X of n integer keys in linear space. Searching X for an integer y means finding the maximum key in X which is smaller than or equal to y. This problem is equivalent to the standard text book problem of maintaining an ordered set. The best previous deterministic linear space bound was O(log n log log n) due to Fredman and Willard from STOC 1990. No better deterministic search bound was known using polynomial space. We also get the following worst-case linear space trade-offs between the number n, the word length W, and the maximal key U Our results are generalized to finger searching and string searching, providing optimal results for both in terms of n.