The Price of Order in the Logarithmic Method
TL;DR
This paper pinpoints the access-model obstruction behind the extra logarithm for exact order and range queries, and the quadratic barrier for select, and bound the product between the total amount of data written during the $n$ insertions and the worst-case amount of data read by a single query, known as the write-read product.
Abstract
The logarithmic method is a classical static-to-dynamic transformation: it stores one dynamic ordered set as several immutable static components and rebuilds them by merges. The same component-and-merge discipline underlies write-optimized ordered indexes, where cheap insertions must be reconciled with exact ordered queries. In this paper, we study the insertion-only version after $n$ insertions, over abstract keys, in a strongly materialized merge-stack model with sequential component merges and one forward scan of the live components per query. We bound the product between the total amount of data written during the $n$ insertions and the worst-case amount of data read by a single query, known as the write-read product. The optimal bounds are as follows: - Membership and local certificates: $\Theta(n\log^2 n)$. - Order and range queries with named keys or endpoints: $\Theta(n\log^3 n)$. - Select: $\Theta(n^2)$. Thus, the logarithmic method does not impose a universal dynamic overhead: under materialized one-way access, the optimum depends on what information the query reveals before the scan starts. This pinpoints the access-model obstruction behind the extra logarithm for exact order and range queries, and the quadratic barrier for select.