Discrete Mathematics and Theoretical Computer Science

DMTCS vol. (subm.):1, by the authors, #rev

Predecessor problem on smooth distributions

arXiv:1511.08598v2 [] 25 Jan 2017

Vladimír Čunát∗
Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic
CZ.NIC, z. s. p. o.

received 2017-01-25,
We follow a research thread studying the predecessor problem on input taken from “smooth” distributions family. We
propose a conceptually simpler solution, utilizing well-known results from much better studied variant of the problem
that assumes nothing about the input. As a side effect, we are able to extend the range of input distributions handled
in O(log log n) time, which are the most studied cases, and we provide better insight into why the related methods
are faster on smooth inputs.
Keywords: data structures, computational complexity, search tree

1

Introduction

The predecessor problem involves maintaining a set of linearly ordered keys and performing queries on
that set. The basic variant allows insertions, deletions, and – more complex to perform – predecessor
query: find the largest contained key that is less than a given value.
This paper investigates the predecessor problem on inputs described by a well studied class of “smooth”
probability distributions. In the following section we formalize models that we use for input and computation, and we introduce the class of smooth distributions. In Section 3 we prove a key property of smooth
distributions that seems to be implicitly used in all related work (in weaker forms) as the most important
step to achieve the stated performance. In Section 4 we show how to utilize this property directly with
well-known distribution-independent structures for the predecessor problem to get better performance in
a simpler way, essentially by converting to the case of polynomial-sized universe.

2

Definitions

We assume the usual word-RAM [7] as our computational model, and additionally we restrict keys to
word-sized integers. That can be shown not to be a significant limitation, as many other key types can
be converted to the integer case cheaply, for example standard floating-point numbers [6, sec. 2.1.3] and
strings [2].
We study the behavior of the predecessor problem in cases where the input has certain specific properties, which requires us to specify how we model the input:
∗ This

research was supported by the Czech Science Foundation under grant GA14-10799S.

ISSN subm. to DMTCS c by the authors by the author(s) Distributed under a Creative Commons Attribution 4.0 International License

2

Vladimír Čunát

Definition 1 (input model). Insertions take keys distributed according to a density µ that does not change
during the whole life of the structure. Deletions remove uniformly from the set of contained elements.
All the operations are arbitrarily intermixed and mutually independent.
This model is convenient because it preserves distribution of the stored set – at any point of execution the set appears like a sample chosen anew according to µ. That is usually essential for simplifying
complexity analyses in related structures. Various random deletion models were thoroughly studied by
Knuth [9].

Most of related papers work with key distributions that can be described as sα , s1−δ -smooth for some
constants α, δ > 0. Typically it is assumed that the particular density of the distribution is not known, but
α and δ are fixed known parameters.
Remark. If the distribution was known and its inverse cumulative distribution function F −1 was cheaply
computable (or approximable), we could convert the problem to the uniform case (or another bounded
density). We could simply store keys transformed by F −1 , which would preserve the order. With any
bounded input distribution, all operations can be easily handled in constant time by simply splitting the
the key domain into Θ(n) intervals and mapping each to an element of an array.(i) This solution for
bounded distributions was pointed out already by Andersson and Mattsson [1, sec. 5.2].
The concept of a smooth probability density was originally introduced by Mehlhorn, Tsakalidis [10]
and later generalized by Andersson, Mattsson [1]. We only amend the definition given in [1, 8] by allowing
c2 = c3 .
Definition 2. Let µ be the density of a continuous random variable X defined over an interval ha, bi.
Given two functions f1 and f2 , µ is called (f1 , f2 )-smooth if
∃β ∀c1 , c2 , c3

a ≤ c1 < c2 ≤ c3 ≤ b ∀s ∈ N




βf2 (s)
c3 − c1
, c2
X ∈ hc1 , c3 i ≤
.
Pr X ∈ c2 −
X∼µ
f1 (s)
s

There is quite a simple intuition behind this complicated condition. It implies that if we cut some
interval hc1 , c3 i into f1 (s) subintervals and generate s values according to density µ restricted to hc1 , c3 i,
every subinterval is expected to get O(f2 (s)) elements.
Remark. This definition, as written, makes only sense for continuous probability distributions, yet any
realistic models of computation can not assume handling arbitrary non-discrete values in constant space
and time per operation. Therefore we assume implicit rounding when inserting a key, thus converting
to the nearest value representable in a single RAM word. It seems reasonable that the related research
assumed something similar without stating it explicitly.

3

Static analysis of bucketing

In this section we show how smoothness implies that an arbitrary sufficiently short interval is expected to
get only a constant number of input keys.

Lemma. Given α, δ > 0 and a positive integer n, let us independently draw n keys from a sα , s1−δ smooth distribution, and split its whole domain into at least nα/δ equally long intervals. Then the expected
number of keys in an interval is O(1).
(i)

We use n to denote the current size of the stored set, following the custom in data structures.

3

Predecessor problem on smooth distributions
Proof: The smoothness (Definition 2) over the domain ha, bi gives us:
∃β ∀c1 , c2 , c3

a ≤ c1 < c2 ≤ c3 ≤ b ∀s ∈ N




βs1−δ
c3 − c1
X
∈
hc
,
c
i
≤
,
c
Pr X ∈ c2 −
= βs−δ .
1
3
2
sα
s

We choose to cover the whole domain hc1 , c3 i := ha, bi. The conditioning can be removed because it is
always fulfilled.



b−a
≤ βs−δ
∃β ∀c2 a < c2 ≤ b ∀s ∈ N Pr X ∈ c2 − α , c2
s
Now we consider splitting the domain into k ≥ nα/δ equally long intervals. Let us choose c2 as the
endpoint of an arbitrary interval I and choose s := bn1/δ c, so sα ≤ nα/δ ≤ k and thus the above
probability covers at least the whole interval I. That gives us:
Pr[X ∈ I] ≤ βs−δ = βbn1/δ c

−δ


−δ
≤ β n1/δ − 1
.

(n1/δ )−δ
= 1, we conclude that Pr[X ∈ I] is O(1/n).
n→∞ (n1/δ − 1)−δ

Since lim

The input keys are chosen independently, so the number of keys in I is given by the binomial distribution,
and its expected value n Pr[X ∈ I] is in O(1).
Remark. We showed that the number of keys in an interval is expected to be constant, but the tail of that
binomial distribution can be bounded even more tightly, e. g. by Chernoff bounds [11, chapter 4.1], to
guarantee that high values are exponentially rare. We do not elaborate on a finer analysis, because we feel
a more pressing problem that we do not solve in this paper – the unrealistic (unmotivated) character of the
used input model where all keys are inserted independently from a (partially) known distribution. We use
those assumptions for our analysis to enable comparison with known structures, as we have only found
one published structure that uses a different model [5] and moreover the bounds implied in that case seem
relatively weak.

4

Combining with known results and comparing to related work

We propose to split the bit representation of every key into two parts, exactly as one step of the decomposition from van Emde Boas trees, except that we split asymmetrically. In both parts we propose to use
standard structures that do not utilize distribution properties of the input. The speed on the more significant bits will be due to the keys being short, and for the less significant bits the number of keys will be
small in expected case due to smoothness.

4.1

Reviewing standard vEBT decomposition

Standard van Emde Boas trees solve the predecessor problem with all operations needing O(log l) time
when working with keys of l bits. That assumes l is not asymptotically larger than the word length of the
used word-RAM.

4

Vladimír Čunát

The well-known decomposition can be viewed as performing binary search for the longest prefix of
bit-representation that is shared by the searched key and some of the stored keys. The structure stores a
mapping from the more significant halves to corresponding subsets of the less significant halves of the
stored keys. These subsets are stored recursively in the same way, and also the set of occurring more
significant halves is stored recursively. The operations on vEBT are carefully designed to perform at most
one nontrivial recursive call on each recursion level, and all the rest are constant-time operations.
To keep the space linear(ii) , some modifications to the original structure are required. The mappings
can be represented by hash tables instead of simple arrays, and indirection can be used: the whole set is
split into Θ(log l)-sized consecutive clusters in a fashion similar to B-tree nodes, and the actual vEBT
construction is only applied to the whole clusters joined together by a doubly linked list. These changes
make the complexity of insertions and deletions expected and amortized where the expectation is only
over random bits.
A possible way of doing these modifications is described in more details e.g. in [4, chapter 4], including
the algorithms for operations which can also be found in textbooks [3, chapter 20].

4.2

Modifying the vEBT decomposition


To cover the cases most studied in previous work, we focus on sα , s1−δ -smooth distributions while
using linear space. To satisfy assumptions of the Lemma, our top-level decomposition needs to split away
at least the most significant (α/δ) log n bits.(iii) If the values of parameters are unknown, we can split
away more bits to be asympotically certain, e.g. log2 n.
These bounds on the number of bits change during the life of the structure, but we can easily ensure
that we cut at least that many by performing a full rebuild after every n0 /4 modifying operations where
n0 denotes the size of the stored set during the last rebuild. It would also be possible to deamortize that
process by standard technique of global rebuilding [12]. Also note that (α/δ) log n > log2 n only for
n < 2α/δ which is an unknown constant; thus the performance will be constant in that
base case.
We can use standard hashed vEBT on the more significant bits to get O log log2 n = O (log log n)
expected amortized time per operation. Each substructure for the less significant bits is expected to store
O(1) keys. The resulting performance is essentially the same as that of Kaporis et al. [8], except that unlike
all previous work we achieve linear space without requiring α ≤ 1, and our approach is conceptually much
simpler.
Main Theorem. There is a structure for solvingthe predecessor problem in O (log log n) expected time
per operation and linear space on any sα , s1−δ -smooth distribution for arbitrary α, δ > 0. The distribution and parameters do not need to be known.

4.3

Concluding remarks

If we wanted to cut down time on unfavorable input, we could use the same
papproach as Kaporis et al.
There are standard structures for the predecessor problem working in time O( log n/ log log n) per operation on arbitrary input (considering the less precise bounds), so these can be used for the less significant
bits. Note that when handling the more significant bits, the expected amortized time O (log log n) remains
independent of the input, as it only comes from randomization during hashing.
(ii)

In word-RAM data structures, linear space means using O(n) words of memory.
In case there are not that many bits in the word, we can “split all of them”, meaning we basically use vEB trees directly while
fitting into the stated complexity bounds.

(iii)

Predecessor problem on smooth distributions

5

We feel that it is good to decouple most of the analysis from complex conditions on the input, as especially in practice we can rarely assume that all operations on the structure are independent and identically
distributed. For the approach of our paper to work, it is enough (informally) that the information is only
carried by a sufficiently short bit prefix of the keys.

Acknowledgements
Most of the results presented above were included in the author’s master thesis [4]. The author wishes to
dedicate this paper to the memory of his supervisor Václav Koubek, who passed away before this work
was completed.

References
[1] A. Andersson, C. Mattsson, Dynamic interpolation search in o(log log n) time, in: Automata, Languages and Programming, Springer, 1993, pp. 15–27.
[2] A. Andersson, M. Thorup, Dynamic string searching, in: Proceedings of the Twelfth Annual ACMSIAM Symposium on Discrete Algorithms, SODA ’01, Society for Industrial and Applied Mathematics, 2001, pp. 307–308.
[3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd Edition, The
MIT Press, 2009.
[4] V. Čunát, Data structures for various distributions of data, Master thesis, Charles University in
Prague, 2010.
[5] E. D. Demaine, T. Jones, M. Pătraşcu, Interpolation search for non-independent data, in: Proceedings
of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, Society for
Industrial and Applied Mathematics, 2004, pp. 529–530.
[6] D. Goldberg, What every computer scientist should know about floating-point arithmetic, ACM
Comput. Surv. 23 (1) (1991) 5–48.
[7] T. Hagerup, Sorting and searching on the word RAM, in: M. Morvan, C. Meinel, D. Krob (Eds.),
STACS 98, Vol. 1373 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1998,
pp. 366–398.
[8] A. Kaporis, C. Makris, S. Sioutas, A. Tsakalidis, K. Tsichlas, C. Zaroliagis, Dynamic interpolation
search revisited, in: 33rd International Colloquium for Automata, Languages and Programming
(ICALP 2006), Vol. 4051 of Lecture Notes in Computer Science, Springer, 2006, pp. 382–394.
[9] D. E. Knuth, Deletions that preserve randomness, in: IEEE Transactions on Software Engineering,
vol.3, no. 5, pp. 351-359, September 1977.
[10] K. Mehlhorn, A. Tsakalidis. Dynamic interpolation search., in: J. ACM, vol. 40, no. 3, pp. 621–634,
Jul. 1993.

6

Vladimír Čunát

[11] R. Motwani, P. Raghavan, Randomized algorithms, Cambridge University Press, New York, USA,
1995.
[12] M. H. Overmars, The Design of Dynamic Data Structures, in: Vol. 156 of Lecture Notes in Computer
Science, Springer-Verlag, 1983, Ch. 5.

