  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.
