Papers for

file system engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

PopTree enables efficient dynamically balanced binary search trees

Dynamically optimal weight-balanced binary search trees

Abstract: In STOC 1972, J{ü}rg Nievergelt and Edward M.~Reingold introduced the $BB[α]$-tree, also known as a \emph{weight-balanced} tree, which for any $α\in (0,\frac{1}{2}]$ is a binary search tree where every node with induced subtree size $s$ has children with induced subtree sizes at least $α(s+1)-1$. A new rotation-based binary search tree, the \emph{PopTree}, is introduced. The PopTree stores $n$ elements and is a $BB[\tfrac1{20}]$-tree after the execution of each search and a $BB[\tfrac1{729}]$-tree at all times, notably while rebalancing. For any constant $α$, its performance on search sequences of length $Ω(n \log n)$ is proved to be within a constant factor (which can depend on $α$) of the optimal offline rotation-based binary search tree that maintains the $BB[α]$ balance invariant.

Wed 21 OctData Structures and Algorithms

The gist

Binary search trees organize data so you can find things quickly, but keeping them balanced is tricky. The authors look at a special kind of balanced tree called a weight-balanced tree that keeps nodes sized just right. They introduce a new tree, the PopTree, which stays balanced dynamically using rotations after each search, without drifting too far from optimal. This means it performs searches nearly as well as the best possible balanced tree even without knowing future queries ahead of time.

Open → 2610.29574v1