A Quick Rundown of the Online List Labeling Problem

The Book Shelf Problem

Imagine I invite you over one day and show you my rather small home library. We decide to play this game:

I empty out my library, and then I give you the books one by one, asking you to put them back in my library in alphabetical order, based on the first letter of each book's title, in the most efficient manner. To see what efficient means in this context, imagine the following scenario:

I give you The Bible, then Voltaire, and you decide to place them at the start of the very first bookshelf in this order: The Bible, Voltaire. Then I hand you Bertrand Russell, and if, say, we're sorting alphabetically by the first letter, you now have to move both The Bible and Voltaire to place Bertrand Russell at the very start of the first bookshelf.

In this scenario, you have to "pay" two movements in order to place Bertrand Russell. This notion of cost is exactly what we're trying to minimize.

To put this more precisely: your goal is to minimize the aggregate number of movements over the total number of inserts I'll ask you to do — you are trying to minimize the amortized cost per insert.

---

Formal Problem Definition

You are given, online, a set of numbers $n$, taken from some universe $U$, and your goal is to place them in an array of size $m > n$. The objective is to minimize the amortized cost per insertion/deletion, where cost is defined by the number of elements moved per insertion or deletion.

---

What is a List Labeling Array?

One of the oldest solutions to the Online List Labeling (OLL) problem dates back to 1981, when Alon Itai et al. designed a priority queue with $O(n \log^2 n)$ total cost for $n$ insertions. This paper would go on to provide a sufficient solution to the OLL problem: just set the priority $p$ of each element $x$ inserted as $p = x$, and you get a solution to the OLL problem with $O(\log^2 n)$ amortized cost per operation.

Here's a simple way to think about a list labeling array:

A Simple List Labeling Array Implementation

Define an array $A$ of size $A = c \times n$ for some constant $c > 1$. Split $A$ into windows of size $\log n$.

These windows form the leaves of an implicit binary tree built on top of the $\frac{c n}{\log n}$ leaves. The root contains the range $[1, c n]$ in the array, and each internal node contains all the elements in its subtree.

For each node $u$ in the tree, define $\text{size}(u)$ as the number of elements in its subarray. We define $\tau_i$ to be the threshold density at depth $i$. In our case, the binary tree has depth $d = \log \frac{c n}{\log n}$.

Let $\tau_0, \tau_d > 0$ be two constants, and define $\tau_i$ by the following recursive formula:

$$\tau_i = \tau_0 + (\tau_d - \tau_0) \frac{i}{d}$$

The core idea is to prevent each node $u$ from exceeding its predefined threshold density $\tau_k$. We enforce this by merging the subarrays of nodes that exceed their threshold density with their siblings and redistributing elements evenly in the resulting subarray. This keeps enough gaps between elements so we do not pay a large cost on every insertion.

Insertion

Insertion is fairly straightforward: to insert some element $x$, we perform a binary search on the binary tree to figure out which window $w_i$ $x$ belongs to, and update $\text{size}(u)$ for each node along the search path. If the window $w_i$ is within threshold, there is always a slot for $x$. Insert $x$ in its slot and rebalance $w_i$ by evenly distributing all elements. If not, go up the tree to find the first ancestor of $w_i$'s node that is within threshold, insert $x$, and rebalance all elements evenly in that range.

Cost and Running Time

This approach achieves both an amortized cost of $O(\log^2{n})$ per insertion and a running time of $O(\log^2{n})$.

Implementation

I also wrote a C implementation while working through the data structure: code.

The implementation follows the theoretical design described above, with the array split into windows of size log n and a balancing tree managing the density of array segments. You can use it by including the header file and creating a new LLA instance with your desired parameters.

#include "lla.h"

int main() {
    // Create LLA with N=1024, C=8, TAU_0=0.5, TAU_D=0.75
    lla *my_lla = create_lla(1024, 8, 0.5, 0.75);
    
    // Insert elements
    insert(my_lla, 10);
    insert(my_lla, 5);
    insert(my_lla, 15);
    
    // Cleanup
    cleanup_lla(&my_lla);
    return 0;
}

The implementation follows the theoretical bounds of O(log²n) insertion time and O(log²n) amortized elements moved per insertion.

References

1. McCauley, S., Moseley, B., Niaparast, A., & Singh, S. (2023). Online List Labeling with Predictions. arXiv:2305.10536