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.
It is a classical result that predecessor searches in bounded universes can be performed in time @math . This was first achieved by van Emde Boas trees @cite_4 , and later by @math -fast tries @cite_12 , and Mehlhorn and N "a her @cite_11 . Of these, van Emde Boas trees use @math space, while the other two structures use @math space.
@cite_4 @cite_12 @cite_11
2152506638 2090021115 2089439745
Abstract Let S denote a set of N records whose keys are distinct nonnegative integers less than some initially specified bound M. This paper introduces a new data structure, called the y- fast trie , which uses Θ ( N ) space and Θ (log log M) time for range queries on a random access machine. We will also define a simpler but less efficient structure, called the x- fast trie . Abstract In this paper we show how to implement bounded ordered dictionaries, also called bounded priority queues, in O(log log N ) time per operation and O( n ) space. Here n denotes the number of elements stored in the dictionary and N denotes the size of the universe. Previously, this time bound required O( N ) space.