Transposition rule approaches optimal list order in polynomial time
Transposition achieves OPT$+O(1)$ in polynomial time for IID list update
Data Structures and AlgorithmsDiscrete Mathematics
Summary
When you have a list of items and want to find things quickly, the best way is to put the most popular items near the front. But if you don't know which items are popular, you can use a simple rule: whenever an item is accessed, swap it one step closer to the front. The authors show that this simple rule gets very close to the best possible ordering after a reasonable number of accesses, even starting from any order. Previous work proved the rule is nearly optimal on average, but this paper shows it works quickly.
What this means in practice
- •For software engineers: Improve search or cache structures that reorder items based on access patterns without knowing item popularity in advance.
- •For database system developers: Design self-adjusting index structures to handle query workloads with unknown item frequencies efficiently.
Authors
Clayton Mizgerd
Abstract
In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$. Items will be queried in an IID manner according to some probability distribution $p$ on the items. We want to minimize the expected cost of each query. The optimal order is to place the items in decreasing order of probability $p_1 \geq p_2 \geq \cdots$ with expected cost $\mathsf{OPT} = \sum_j j p_j$, but the probability vector $p$ is generally unknown. Thus we use a self-organizing list following the transposition rule: an item is transposed 1 position forward whenever it is queried. Coester (2026) proved that, at stationarity measure for the transposition rule, the expected cost of a query is at most $\mathsf{OPT} + 1$. However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $σ$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.