Predecessor problem

In

The predecessor problem is a simple case of the nearest neighbor problem, and data structures that solve it have applications in problems like integer sorting.

Definition

The problem consists of maintaining a set S, which contains a subset of U integers. Each of these

of w, implying that ${\displaystyle U\leq 2^{w}}$. Data structures that solve the problem support these operations:^[2]

• predecessor(x), which returns the largest element in S less than or equal to x
• successor(x), which returns the smallest element in S greater than or equal to x

In addition, data structures which solve the dynamic version of the problem also support these operations:

• insert(x), which adds x to the set S
• delete(x), which removes x from the set S

The problem is typically analyzed in a transdichotomous model of computation such as word RAM.

Data structures

One simple solution to this problem is to use a

of ${\displaystyle O(\log n)}$ for predecessor queries. The Van Emde Boas tree achieves a query time of ${\displaystyle O(\log \log U)}$, but requires ${\displaystyle O(U)}$ space.^[1] Dan Willard proposed an improvement on this space usage with the x-fast trie, which requires ${\displaystyle O(n\log U)}$ space and the same query time, and the more complicated y-fast trie, which only requires ${\displaystyle O(n)}$ space.^[3] Fusion trees, introduced by Michael Fredman and Willard, achieve ${\displaystyle O(\log _{w}n)}$ query time and ${\displaystyle O(n)}$ for predecessor queries for the static problem.^[4] The dynamic problem has been solved using exponential trees with ${\displaystyle O(\log _{w}n+\log \log n)}$ query time,

expected time

${\displaystyle O(\log _{w}n)}$ using hashing.^[6]

Mathematical properties

There have been a number of papers proving

Big Theta notation

) ${\displaystyle \Omega \left({\tfrac {\log w}{\log \log w}}\right)}$, and similarly, for all values of n, there exists a value of n such that the query time is ${\displaystyle \Omega \left({\sqrt {\tfrac {\log n}{\log \log n}}}\right)}$.^[1] Other proofs of lower bounds include the notion of communication complexity.

For the static predecessor problem, Mihai Pătrașcu and Mikkel Thorup showed the following lower bound for the optimal search time, in the cell-probe model:^[7]

$${\displaystyle O(1)\min \left\{{\begin{array}{l}\log _{w}n\\\lg {\frac {\ell -\lg n}{a}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left({\frac {a}{\lg n}}\,\cdot \,\lg {\frac {\ell }{a}}\right)}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left(\lg {\frac {\ell }{a}}\right/\left.\lg {\frac {\lg n}{a}}\right)}}\end{array}}\right.}$$

where the RAM has word length ${\displaystyle w}$, the set contains ${\displaystyle n}$ integers of ${\displaystyle \ell }$ bits each and is represented in the RAM using ${\displaystyle S}$ words of space, and defining ${\displaystyle a=\lg {\frac {S}{n}}+\lg w}$.

In the case where ${\displaystyle w=\ell =\gamma \lg n}$ for ${\displaystyle \gamma >1}$ and ${\displaystyle S=n\cdot \lg ^{O(1)}n}$, the optimal search time is ${\displaystyle \Theta (\lg \ell )}$ and the van Emde Boas tree achieves this bound.^[7]

See also

• Integer sorting
• y-fast trie
• Fusion tree

References

1. ^
   S2CID 1991980
   .
2. ^ Rahman, Naila; Cole, Richard; Raman, Rajeev (17 August 2001). Optimized Predecessor Data Structures for Internal Memory (PDF). International Workshop on Algorithm Engineering. pp. 67–78.
3. doi:10.1016/0020-0190(83)90075-3
   .
4. ^ Fredman, Michael; Willard, Dan (1990). "Blasting through the information theoretic barrier with fusion trees". Symposium on Theory of Computing: 1–7.
5. S2CID 8175703
   .
6. MR 1469229
   .
7. ^
   S2CID 1232
   .