Online List Labeling: Breaking the log2 n Barrier

The online list labeling problem is a basic primitive in data structures. The goal is to store a dynamically-changing set of n items in an array of m slots, while keeping the elements in sorted order. To do so, some items may need to be moved over time, and the goal is to minimize the number of items moved per insertion/deletion. When m=Cn for some constant C>1, an upper bound of O(log2n)items moved per insertion/deletion has been known since 1981. There is a matching lower bound for deterministic algorithms, but for randomized algorithms, the best known lower bound is Omega(log n), leaving a gap between upper and lower bounds. We improve the upper bound, providing a randomized data structure with expected O(log3/2n) items moved per insertion/deletion.

Joint work with Michael Bender, Alexander Conway, Martin Farach-Colton, Hanna Komlos, and William Kuszmaul