Online List Labeling: Breaking the log2n Barrier

The online list-labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing set of n items in an array of m slots, while maintaining the invariant that the items appear in sorted order, and while minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. For the linear regime, where $m = (1+\Theta(1))n$, an upper bound of $O(\log^{2}n)$ on the relabeling cost has been known since 1981. A lower bound of $\Omega(\log^{2}n)$ is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains $\Omega(\log n)$. The central open question in the field is whether $O(\log^{2}n)$ is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of $O(\log^{3/2}n)$ per operation. More generally, if $m=(1+\varepsilon)n$ for $\varepsilon=O(1)$, the expected relabeling cost becomes $O(\varepsilon^{-1}\log^{3/2}n)$. Our solution is history independent, meaning that the state of the data structure is independent of the order in which items are inserted/deleted. For history-independent data structures, we also prove a matching lower bound: for all $\varepsilon$ between $1/n^{1/3}$ and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is $\Theta(\varepsilon^{-1}\log^{3/2}n)$.