BIASED PREDECESSOR SEARCH*

arXiv:1707.01182v1 [] 4 Jul 2017

Prosenjit Bose,† Rolf Fagerberg,‡ John Howat,† and Pat Morin†

Abstract. 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.
Keywords: data structures, predecessor search, biased search trees, entropy

1 Introduction
The notion of biased searching has received significant attention in the literature on ordered
dictionaries. In ordered dictionaries, the central operation is predecessor queries—that is,
queries for the largest element stored in the data structure that is smaller than a given
query value. The setting is biased when each element i of the data structure has some
probability pi of being queried, and we wish for queries to take a time related to the inverse
of the probability of that query. For example, a biased search tree [5] can answer a query
for item i in time O(log 1/pi ).1 For biased predecessor queries, also the gaps between
consecutive elements of the data structure are assigned probabilities of being searched for
P
[11, 5, p. 564]. Recall that i pi log(1/pi ) is the entropy of the distribution of queries. In
terms of this quantity, we note that the expected query time in a biased search tree is linear
in the entropy of the query distribution, and that this is optimal for binary search trees [5,
Thm. A].2
Binary search trees work in the comparison-based setting where keys only can be
accessed by comparisons. Predecessor searches have also been researched extensively in
the context of bounded universes where keys are integers of bounded range whose bits may
* Partially supported by the Danish Council for Independent Research, Natural Sciences, grant DFF-132300247.
† Carleton University, {jit,jhowat,morin}@scs.carleton.ca
‡ University of Southern Denmark, rolf@imada.sdu.dk
1 In this paper, we define log x = log (x + 2).
2
2 As will be apparent from our results, in bounded universes this lower bound does not hold, and one can
achieve query times below it.

1

be accessed individually. More precisely, let U = {0, 1, . . . , U − 1} be the universe of possible
keys, and consider a static subset S = {s1 , s2 , . . . , sn } ⊆ U , where s1 < s2 < · · · < sn . Predecessor
searches in this context admit data structures with query times that are not only a function
of n, but also of U . For example, van Emde Boas trees [16] can answer predecessor queries
in time O(log log U).
A natural question—but one which has been basically unexplored—is how to combine these two areas of study to consider biased searches in bounded universes. In this
setting, we have a probability distribution D = {p0 , p1 , . . . , pU −1 } over the universe U such
P −1
that the probability of receiving i ∈ U as a query is pi and U
i=0 pi = 1. We wish to preprocess U and S, given D, such that the time for a query is related to D.
P −1
The motivation for such a goal is the following. Let H = U
i=0 pi log(1/pi ) be the
entropy of the distribution D. Recall that the entropy of a U -element distribution is between 0 and log U . Therefore, if an expected query time of O(logH) can be achieved, this
for any distribution will be at most O(log logU ), which matches the performance of van
Emde Boas trees [16]. However, for lower-entropy distributions, this will be faster—as a
concrete example, an exponential distribution (say, pi = Θ(1/2i )) has H = O(1) and will
yield support of queries in expected constant time. In other words, such a structure will
allow bias in the query sequence to be exploited for ordered dictionaries over bounded
universes. Hence, perhaps the most natural way to frame the line of research in this paper is by analogy: the results here are to biased search trees as van Emde Boas trees (and
similar structures) are to binary search trees.
Our results. The results presented here can be divided into four categories. In the first
we give two variants of a data structure that obtains O(log H) query time but space that
is bounded in terms of U . In the
we give a solution that obtains space that is

√ second
linear in n but has query time O H . In bounded universe problems, n is always smaller
than U (often substantially so), so these two categories can be seen as representing a timespace trade-off. In the third we consider individual query times on universe elements with
general weights. In the fourth we consider query times related to the working-set number
(which is defined as the number of distinct predecessors reported since the last time a
particular predecessor was reported), so that the query distribution need not be known
in advance. Our methods use hashing and existing (unbiased) predecessor structures for
bounded universes [3, 17] as building blocks.
Organization. The rest of the paper is organized in the following way. We first complete
the current section by reviewing related work. In Section 2 we show how to obtain good
query times at the expense of large space. In Section 3 we show how to obtain good space
at the expense of larger query times. We conclude in Section 4 with a summary of the
results obtained and possible directions for future research.

2

1.1

Related Work

It is a classical result that predecessor searches in bounded universes can be performed in
time O(log log U). This was first achieved by van Emde Boas trees [16], and later by y-fast
tries [17], and Mehlhorn and Näher [13]. Of these, van Emde Boas trees use O(U ) space,
while the other two structures use O(n) space.
These bounds can be improved to

s







log n 

 loglog U

,
O min 





 log loglog U
log log n 
using nO(1) space [3]. By paying an additional O(log log n) factor in the first half of this
bound, the space can be improved to O(n) [3]. Pătraşcu and Thorup later effectively settled
this line of research with a set of time-space trade-offs [14].
Departing the bounded universe model for a moment and considering only biased
search, perhaps the earliest such data structure is the optimum binary search tree [11],
which is constructed to be the best possible static binary search tree for a given distribution. Optimum binary search trees take a large amount of time to construct; in linear time,
however, it is possible to construct a binary search tree that answers queries in time that is
within a constant factor of optimal [12]. Even if the distribution is not known in advance,
it is still possible to achieve the latter result (e.g., [2, 15]).
Performing biased searches in a bounded universe is essentially unexplored, except for the case where the elements of S are drawn from D rather than the queries [4].
In that result, D need not be known, but must satisfy certain smoothness constraints,
and
time with high probability and
 is given that supports O(1) query

p a data structure
1+ǫ
bits of space, which can be reO log n/ log log n worst-case query time, using O n
duced to O(n) space at the cost of a O(log log n) query time (with high probability). It is
worth noting that this data structure is also dynamic.
A related notion is to try to support query times related to the distribution in a
p
less direct way. For example, finger searching can be supported in time O log d/ log log d
where d is the number of keys stored between a finger pointing at a stored key and the
query key [1]. There is also a data structure that supports such searches in expected time
O(log log d) for a wide class of input distributions [10]. Finally, a query time of O(log log ∆),
where ∆ is the difference between the element queried and the element returned, can also
be obtained [7].
Other problems in bounded universes can also be solved in similar ways. A priority
queue that supports insertion and deletion in time O(log log d ′ ), where d ′ is the difference
between the successor and predecessor (in terms of priority) of the query, is known [9],
as well as a data structure for the temporal precedence problem, wherein the older of two
query elements must be determined, that supports query time O(log log δ), where δ is the
3

temporal distance between the given elements [8].

2 Supporting O(log H) Query Time
In this section, we describe how to achieve query time O(log H) using space that is bounded
in terms of U .
2.1

Using O(n + U ǫ ) Space

Let ǫ > 0. We place all elements i ∈ U with probability pi ≥ (1/U )ǫ into a hash table T , and
with each element we store a pointer to its predecessor in S (which never changes since
S is static). All elements of S are also placed into a y-fast trie over the universe U . Since
there are at most U ǫ elements with probability greater than (1/U )ǫ , it is clear that the hash
table requires O(U ǫ ) space. Since the y-fast trie requires O(n) space, we have that the total
space used by this structure is O(n + U ǫ ). To execute a search, we check the hash table
first. If the query (and thus the answer) is not stored there, then a search is performed in
the y-fast trie to answer the query.
The expected query time is thus
X
X
pi O(1) +
pi O(log log U )
i∈T

= O(1) +

X
i∈U \T

= O(1) +

X

i∈U \T

= O(1) +

X

i∈U \T

pi O(log log U)



pi O log log (U ǫ )1/ǫ
pi O(log((1/ǫ) logU ǫ ))

i∈U \T

= O(1) +

X

pi O(log(1/ǫ)) +

i∈U \T

= O(1) + O(log(1/ǫ)) +

i∈U \T

X
i∈U \T

≤ O(1) + O(log(1/ǫ)) +

X

X

pi O(log log U ǫ )


pi O log log

1
1/U ǫ



pi O(log log(1/pi ))

i∈U \T

The last step here follows from the fact that, if i ∈ U \T , then pi ≤ (1/U )ǫ , and so 1/(1/U )ǫ ≤
1/pi . Recall Jensen’s inequality, which states that for concave functions f , E[f (X)] ≤
f (E[X]). Since the logarithm is a concave function, we therefore have
X
X
pi O(log log(1/pi )) ≤ log
pi O(log(1/pi )) ≤ O(log H)
i∈U \T

i∈U \T

therefore, the expected query time is O(log(1/ǫ)) + O(log H) = O(log(H/ǫ)).

4

Theorem 1. Given a probability distribution with entropy H over the possible queries in a
universe of size U , it is possible to construct a data structure that performs predecessor searches
in expected time O(log(H/ǫ)) using O(n + U ǫ ) space for any ǫ > 0.
Theorem 1 is a first step towards our goal. For ǫ = 1/2, for example, we achieve
O(log H) query time, as desired, and our space usage is O(n) + o(U ). This dependency on
U , while sublinear, is still undesirable. In the next section, we will see how to reduce this
further.
2.2



ǫ
Using O n + 2log U Space

To improve the space used by the data structure described in Theorem 1, one observation
is that we can more carefully select the threshold for “large probabilities” that we place
ǫ
logǫ U for some 0 < ǫ < 1. The space
in the hash table. Instead of (1/U
 ) , ǫwe can use (1/2)
used by the hash table is thus O 2log U , which is o(U ǫ ) for any ǫ > 0. The analysis of the
expected query times carries through as follows
X
X
X
pi O(1) +
pi O(log log U) = O(1) +
pi O(log log U)
i∈T

i∈U \T

i∈U \T

= O(1) +

X

i∈U \T

= O(1) +

X

i∈U \T

= O(1) +

X

pi ǫ(1/ǫ)O(log log U)
pi (1/ǫ)O(log (logǫ U ))



ǫ
pi (1/ǫ)O log log 2log U

i∈U \T

≤ O(1) +

X

i∈U \T

≤ O(1) + (1/ǫ)

pi (1/ǫ)O(log log(1/pi ))
X

pi O(log log(1/pi ))

i∈U \T

≤ O((1/ǫ) log H)

Theorem 2. Given a probability distribution with entropy H over the possible queries in a
universe of size U , it is possible to construct
structure that performs predecessor searches
 a data
ǫ
log
U
space for any 0 < ǫ < 1.
in expected time O((1/ǫ) log H) using O n + 2
2.3

Individual Query Times for Elements

Observe that part of the proof of Theorem 2 is to show that an individual query for an
element i ∈ U \ T can be executed in time O((1/ǫ) log log1/pi ) time. Since the query time of
elements in T is O(1), the same holds for these. More generally, the structure can support
arbitrarily weighted elements in U . Suppose each element i ∈ U has a real-valued weight
P −1
wi > 0 and let W = U
i=0 wi . By assigning each element probability pi = wi /W , we achieve
5

an individual query time of O((1/ǫ) loglog(W /wi )), which is analogous to the O(logW /wi )
query time of biased search trees [5]. Since the structure is static, we can use perfect
hashing for the hash tables involved (T as well as those in the y-fast trie), hence the search
time is worst-case.
Theorem 3. Given a positive real weight wi for each element i in a universe of size U , such that
the sum of all weights is W , it is possible to construct a data structure that
 a predecessor
 performs
ǫ
log
U
space for any
search for item i in worst-case time O((1/ǫ) loglog(W /wi )) using O n + 2
0 < ǫ < 1.

3 Supporting O(n) Space
In this section, we describe how to achieve space O(n) by accepting a larger query time
√
O H . We begin with a brief note concerning input entropy vs. output entropy.
Input vs. Output Distribution. Until now, we have discussed the input distribution, i.e.,
the probability pi that i ∈ U is the query. We could also discuss the output distribution,
i.e., the probability pi∗ that i ∈ U is the answer to the query. This distribution is defined by
Psk+1 −1
pi∗ = 0 if i < S and pi∗ = j=s
pj if i ∈ S = {s1 , s2 , . . . , sn } with i = sk .
k


∗
Suppose we can answer a predecessor query for i in time O log log1/ppred(i)
where
pred(i) is the predecessor of i. Then the expected query time is
X


∗
pi O log log1/ppred(i)
i∈U

P
∗
Since pi ≤ ppred(i)
for all i, this is at most i∈U pi log log 1/pi , i.e., the entropy of the input
distribution. It therefore suffices to consider the output distribution.
Our data structure will use a series of data structures for predecessor search [3] that
increase doubly-exponentially in size in much the same way as the working-set structure
[2]. Recall from Section 1.1 that there exists a linear
that is able to

q
 space data structure
execute predecessor search queries in time O min

log log n·log log U
log log log U ,

log n
log log n

[3]. We will

maintain several such structures D1 , D2 , . . ., where each Dj is over the universe U and stores
j

22 elements of S. In more detail, sorting the elements of S by probability into decreasing
1
2
order, we store the first 22 elements in D1 , the next 22 elements in D2 , etc. In general, Dj
j

contains the 22 elements of highest probability that are not contained in any Dk for k < j.
Note that here, “probability” refers to the output probability.
Searches are performed by doing a predecessor search in each of D1 , D2 , . . . until the
answer is found. Along with each element we store a pointer to its successor in S. When
we receive the predecessor of the query in Dj , we check its successor to see if that successor
is larger than the query. If so, the predecessor in Dj is also the real predecessor in S (i.e.,
the answer to the query), and we stop the process. Otherwise, the real predecessor in S is
6

somewhere between the predecessor in Dj and the query, and can be found by continuing
to Dj+1 , Dj+2 , . . .. This technique is known from [6].
We now consider the search time in this data structure. Suppose the process stops
by finding the correct predecessor of the query i in Dj where j > 1 (otherwise, the prej−1

decessor was found in D1 in O(1) time). Dj−1 contains 22 elements all of which have
∗
(output) probability at least ppred(i)
. Since the sum of the probabilities of these elements


j−1
∗
∗
is at most one, it follows that ppred(i) ≤ 1/22 . Equivalently, j is O loglog 1/ppred(i)
. The
total time spent searching is bounded by
s
s 
j
j r

q
k
 2j 
X
X
log 22
2k
 = O log 1/p ∗

(1)
=
O
=
 j 
k
pred(i)
k
log log22
k=1

k=1

The second equality above follows because the terms of the summation are exponentially
∗
increasing and hence the last term dominates the entire sum. Therefore, since pi ≤ ppred(i)
for all i, the expected query time is
X q
X p
√
∗
pi log1/ppred(i)
≤
pi log 1/pi ≤ H
i∈U

i∈U

The final step above follows from Jensen’s inequality. To determine the space used by this
data structure, observe that every element stored in S is stored in exactly one Dj . Since
each Dj uses space linear in the number of elements stored in it, the total space usage is
O(n).
Theorem 4. Given a probability distribution with entropy H over the possible queries in a
universe of size U , it√is possible
to construct a data structure that performs predecessor searches

in expected time O H using O(n) space.
Observe that we need not know the exact distribution D to achieve the result of
Theorem 4; it suffices to know the sorted order of the keys in terms of non-increasing
probabilities.
Also observe that like in Section 2.3, the structure here can support arbitrarily
weighted elements. Suppose each element i ∈ U has a real-valued weight wi > 0 and let
P −1
W = U
i=0 wi . By assigning each element probability pi = wi /W , we see that (1) and the
∗
fact that pi ≤ ppred(i)
for all i give the following.
Theorem 5. Given a positive real weight wi for each element i in a bounded universe, such
that the sum of all weights is W , it is possible to
pconstruct adata structure that performs a
predecessor search for item i in worst-case time O log(W /wi ) using O(n) space.
Furthermore, since the predecessor search structure used for the Dj ’s above is in
fact dynamic [3], we can even obtain a bound similar to the working-set
property: a pre
p
decessor search for item i can be answered in time O logw(i) where w(i) is the number
7

of distinct predecessors reported since the last time the predecessor of i was reported.
This can be accomplished using known techniques [2], similar to the data structure of
Theorem 4, except that instead of ordering the elements of S by their probabilities, we
order them in increasing order of their working-set numbers w(i). Whenever an element
from Dj is reported, we move the element to D1 and for k = 1, 2, . . . , j − 1 shift one element
from Dk to Dk+1 in order to fill the space left in Dj while keeping the ordering based on
j−1

w(i), just as in the working-set structure [2]. All 22 elements in Dj−1 have been reported
more recently than the current element reported from Dj , so an analysis similar to (1)

p
shows that queries are answered in O log w(i) time. The structure uses O(n) space.
Theorem 6. Let w(i) denote the number of distinct predecessors reported since the last time the
predecessor of i was reported, or n if the predecessor of i has not yet been reported. It is possible
toconstruct
a data structure that performs a predecessor search for item i in worst-case time
p
O log w(i) using O(n) space.

4 Conclusion
In this paper, we have introduced the idea of biased predecessor search in bounded universes. Two different categories of data structures were considered: one with query times
that are logarithmic in the entropy of the query distribution (with space that is a function
of U ), and one with linear space (with query times larger than logarithmic in the entropy).
We also considered the cases of individual query times on universe elements with general
weights and of query times related to the working-set number.
Our results leave open several possible directions for future research:
1. Is it possible to achieve O(logH) query time and O(n) space?
2. The reason for desiring a O(log H) query time comes from the fact that H ≤ log U
and the fact that the usual data structures for predecessor searching have query
time O(log log U ). Of course, this is not optimal: other results have since improved
this upper bound [3, 14]. Is it possible to achieve a query time of, for example,
O(log H/ log log U)?
3. What lower bounds can be stated in terms of either the input or output entropies?
Clearly O(U ) space suffices for O(1) query time, and so such lower bounds must
place restrictions on space usage.

References
[1] A. Andersson and M. Thorup. Dynamic ordered sets with exponential search trees.
Journal of the ACM, 54(3):Article 13, 2007.

8

[2] Mihai Bădoiu, Richard Cole, Erik D. Demaine, and John Iacono. A unified access
bound on comparison-based dynamic dictionaries. Theoretical Computer Science,
382(2):86–96, 2007.
[3] Paul Beame and Faith E. Fich. Optimal bounds for the predecessor problem and
related problems. Journal of Computer and System Sciences, 65(1):38–72, 2002.
[4] D. Belazzougui, A.C. Kaporis, and P.G. Spirakis. Random input helps searching predecessors. arXiv:1104.4353, 2011.
[5] Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan. Biased search trees. SIAM
Journal on Computing, 14(3):545–568, 1985.
[6] Prosenjit Bose, John Howat, and Pat Morin. A distribution-sensitive dictionary with
low space overhead. In Proceedings of the 11th International Symposium on Algorithms
and Data Structures (WADS 2009), LNCS 5664, pages 110–118, 2009.
[7] Prosenjit Bose, Karim Douı̈eb, Vida Dujmović, John Howat, and Pat Morin. Fast local searches and updates in bounded universes. In Proceedings of the 22nd Canadian
Conference on Computational Geometry (CCCG 2010), pages 261–264, 2010.
[8] Gerth Stølting Brodal, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, and
Kostas Tsichlas. Optimal solutions for the temporal precedence problem. Algorithmica, 33(4):494–510, 2002.
[9] Donald B. Johnson. A priority queue in which initialization and queue operations
take O(log log D) time. Theory of Computing Systems, 15(1):295–309, 1981.
[10] Alexis Kaporis, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, Kostas
Tsichlas, and Christos Zaroliagis. Improved bounds for finger search on a RAM.
In ESA ’03: Proceedings of the 11th Annual European Symposium on Algorithms, LNCS
2832, pages 325–336, 2003.
[11] D.E. Knuth. Optimum binary search trees. Acta Informatica, 1(1):14–25, 1971.
[12] Kurt Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5(4):287–295,
1975.
[13] Kurt Mehlhorn and Stefan Näher. Bounded ordered dictionaries in O(log log N ) time
and O(n) space. Information Processing Letters, 35(4):183–189, 1990.
[14] Mihai Pătraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. In
STOC ’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing,
pages 232–240, 2006.
[15] Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees.
Journal of the ACM, 32(3):652–686, 1985.
[16] P. van Emde Boas. Preserving order in a forest in less than logarithmic time and
linear space. Information Processing Letters, 6(3):80–82, 1977.
9

[17] Dan E. Willard. Log-logarithmic worst-case range queries are possible in space
Θ(log log N ). Information Processing Letters, 17(2):81–84, 1983.

10

