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(log2 n) on the relabeling cost has been known since 1981. A lower bound of Omega(log2 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(log2 n) is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of O(log3/2 n) per operation. More generally, if m = (1 + varepsilon) n for varepsilon = O(1), the expected relabeling cost becomes O(varepsilon-1 log3/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 ε between 1 / n1/3 and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is Theta(varepsilon-1log3/2 n).