Dynamic Partial Sorting

Jiamou Liu, Kostya RossarXiv 2014 · arXiv

Introduction

In modern data management, we often encounter datasets that are both massive and highly volatile. Consider a library database where books are indexed by category and ranked by popularity. A user might request the top 10 most popular books in "Science Fiction." However, this list is a moving target: new books are added, categories are merged or split, and borrow counts fluctuate daily.

Standard data structures like self-balancing Binary Search Trees (BSTs) excel at key-based lookups but struggle with value-based order statistics. Conversely, static selection algorithms like Quickselect are efficient but require a full re-computation whenever the underlying data changes. This paper formalizes these requirements as the Dynamic Partial Sorting problem, seeking a structure that supports efficient top-$k$ queries alongside updates, concatenations (link), and splits (cut).

The Dynamic Partial Sorting Problem

The authors define four primary operations for a list $\ell$:

  1. psort(ℓ, k): Return the $k$ smallest elements in increasing order.
  2. changeval(ℓ, x, x'): Update the value of element $x$ to $x'$.
  3. link(ℓ_i, ℓ_j): Concatenate two lists.
  4. cut(ℓ, x): Split a list into two at a specific element.

While naive approaches like linked lists or priority queues offer trade-offs (fast updates vs. fast queries), they fail to provide efficient performance across all four operations simultaneously, particularly for link and cut operations which often scale linearly with the list size $n$.

Tournament Trees and the Principal Path

A foundational step toward the solution is the Tournament Tree (TT). A TT is a balanced binary tree where leaves represent list elements and internal nodes store the minimum value of their children. The root always contains the minimum element of the entire list.

A Tournament Tree structure illustrating the principal path (bold) to the minimum element and its subordinates.

A key insight is the Principal Path concept. The minimum element defines a path from a leaf to the root. Every node on this path has a "subordinate" (the sibling node that "lost" the local match). Crucially, the second-smallest element in the list must be the minimum of these subordinates. This observation allows for a query mechanism that extracts elements by iteratively exploring these subordinates.

The Innovation: Layered Tournament Trees (LTT)

To overcome the $O(k \log n)$ query bottleneck of standard Tournament Trees, the authors introduce the Layered Tournament Tree (LTT). This recursive structure organizes the subordinates of a principal path into their own tournament trees in a lower layer.

Instead of traversing a single massive tree, the psort algorithm can "jump" between layers. Because each successive layer is significantly smaller than the one above it, the total number of layers is bounded by the iterated logarithm ($\log^* n$). This function grows so slowly that it is effectively a small constant (e.g., $\log^* n \le 6$ for $n=1,000,000$), making the query time nearly independent of the total list size $n$.

Algorithm 1: The psort procedure for extracting the top-k elements using a priority queue of subordinates.

Complexity Analysis and Results

The paper provides a rigorous mathematical proof of the LTT's efficiency. By replacing the $\log n$ factor in queries with $\log^* n$, the LTT offers a significant speedup for massive datasets. The table below compares the asymptotic complexities:

Operation Tournament Tree (Standard) Layered Tournament Tree (Proposed)
Query (psort) $O(k \log n)$ $O(\log^*_\phi(n) \cdot k \log k)$
Updates $O(\log n)$ $O(\log n \cdot \log^2(\log n))$

While the update operations are slightly more complex than those of a standard TT, the trade-off is justified by the near-constant query overhead relative to $n$. For a list of one million elements, the LTT query is substantially faster as the $\log n$ factor (approx. 20) is replaced by the much smaller $\log^* n$ (approx. 6).

Conclusion

The Layered Tournament Tree represents a significant theoretical advancement in dynamic data structures. By leveraging recursive layering and the principal path property, the authors decouple the cost of partial sorting from the total size of the dataset. While the implementation complexity is higher than traditional trees, the LTT provides a robust solution for applications requiring real-time top-$k$ results in rapidly changing, large-scale environments.

Summary updated

Abstract

The dynamic partial sorting problem asks for an algorithm that maintains lists of numbers under the link, cut and change value operations, and queries the sorted sequence of the $k$ least numbers in one of the lists. We first solve the problem in $O(k\log (n))$ time for queries and $O(\log (n))$ time for updates using the tournament tree data structure, where $n$ is the number of elements in the lists. We then introduce a layered tournament tree data structure and solve the same problem in $O(\log_\varphi^* (n) k\log (k))$ time for queries and $O\left(\log (n)\cdot\log^2\log (n)\right)$ for updates, where $\varphi$ is the golden ratio and $\log_\varphi^*(n)$ is the iterated logarithmic function with base $\varphi$.
BibTeX
@misc{liu2014dynamic,
  author = {Jiamou Liu and Kostya Ross},
  title = {{Dynamic Partial Sorting}},
  year = {2014},
  eprint = {1402.2712},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.2712},
}
Figure