A Faster External Memory Priority Queue with DecreaseKeys

Shunhua Jiang, Kasper Green Larsen

TL;DR

This paper introduces a novel external memory priority queue that significantly speeds up operations, particularly when keys need their priorities updated (DecreaseKey). It achieves an expected amortized I/O complexity of $O(\frac{\log B}{\log \log N})$, closing a long-standing gap between theoretical lower bounds and practical performance for this crucial data structure. This improvement also directly benefits external memory algorithms like Dijkstra's for shortest path computations.

What Problem Does This Paper Address?

In modern computing, data often exceeds the capacity of fast main memory, necessitating the use of slower, larger external storage (like disks). Algorithms operating on this data are bottlenecked by the number of I/O operations (transfers between main memory and disk). A priority queue is a fundamental data structure for managing ordered elements, essential for algorithms like Dijkstra's for shortest paths.

The challenge lies in designing efficient priority queues for this "external memory model." While priority queues without a "DecreaseKey" operation (where you can efficiently update an existing element's priority) can achieve $O(\frac{\log B}{\log \log N})$ I/Os per operation, those supporting DecreaseKey were stuck at $O(\frac{\log B}{B})$ I/Os. This gap was recently highlighted by a lower bound proving that DecreaseKey operations inherently require more I/Os, specifically $\Omega(\frac{\log B}{\log \log N})$. This paper tackles the problem of bridging this gap, aiming to achieve the optimal $O(\frac{\log B}{\log \log N})$ I/O complexity for priority queues that do support DecreaseKey.

Methods

The authors build upon the existing external memory tournament tree structure. Their key innovation is a new data structure that uses a t-ary tree where the branching factor $t$ is carefully chosen as $t = \log^{0.01} N$. This increased branching factor reduces the tree's height to $O(\frac{\log N}{\log t}) = O(\frac{\log B}{\log \log N})$.

To manage I/O efficiently, each node in this tree employs several clever techniques:

  • Bloom Filter Replacement: Each node stores a Bloom filter to quickly check for the presence of keys without loading entire blocks of data. This allows for approximate membership testing with a low false positive rate.
  • Signal Buffers and Todo Buffers: Nodes use buffers to temporarily store signals (like Insert, Delete, Update) destined for their children or for their own entries. These buffers are flushed to children or applied to entries only when they overflow, amortizing the I/O cost.
  • Boundary Values: Each node maintains a boundary value that helps enforce heap order and guide signal propagation.

The core idea is to avoid reading entire blocks of data unless absolutely necessary. By using Bloom filters and carefully managing signal propagation through buffers, the structure can make decisions about where signals should go with minimal I/O.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • DecreaseKey is Fundamentally More Expensive: The paper reinforces the finding that supporting DecreaseKey operations inherently requires more I/O than simpler operations. This is due to the difficulty of efficiently locating and updating an element's priority without knowing its current value.
  • Balancing Tree Height and Node Complexity: The optimal I/O complexity is achieved by a delicate balance. Increasing the tree's branching factor reduces height, but also increases the cost of processing a node. The authors find the sweet spot by setting $t$ based on a logarithm of $N$.
  • Bloom Filters as a Lightweight Check: Bloom filters are crucial for making quick, probabilistic decisions about key presence, avoiding costly disk reads for every potential operation. The low false positive rate is key to maintaining correctness.
  • Amortization Through Buffering: The use of signal and todo buffers is a classic external memory technique, but here it's applied in a sophisticated way to manage the complexity introduced by DecreaseKey.

Key Results

The paper presents a new external memory priority queue that supports Insert, Delete, ExtractMin, and DecreaseKey operations with an expected amortized I/O complexity of $O(\frac{\log B}{\log \log N})$. This matches the theoretical lower bound for priority queues with DecreaseKey, improving upon previous $O(\frac{\log B}{B})$ solutions.

As a direct application, this improved priority queue leads to the fastest external memory algorithm for the Single Source Shortest Path (SSSP) problem on general graphs, achieving $O(|V| + |E|\frac{\log B}{\log \log |V|})$ I/Os.

Limitations and Future Work

  • Key Type Assumption: The main result assumes keys are integers in $\{1, \dots, N\}$. While the paper notes this is a common assumption, extending it to arbitrary keys might require further work.
  • Cache-Oblivious Model: The authors explicitly state they did not extend their priority queue to the cache-oblivious model, which analyzes performance independent of specific cache/memory sizes ($M$ and $B$). This is a natural direction for future research.
  • Lower Bound Gap: While the paper closes the gap for priority queues with DecreaseKey, there remains a gap between their $O(\frac{\log B}{\log \log N})$ result and the $\Omega(\frac{\log B}{\log \log N})$ lower bound for priority queues without DecreaseKey. The authors suggest it would be exciting to design a matching priority queue for the latter case.

Summary updated

Abstract

A priority queue is a fundamental data structure that maintains a dynamic set of (key, priority)-pairs and supports Insert, Delete, ExtractMin and DecreaseKey operations. In the external memory model, the current best priority queue supports each operation in amortized I/Os. If the DecreaseKey operation does not need to be supported, one can design a more efficient data structure that supports the Insert, Delete and ExtractMin operations in I/Os. A recent result shows that a degradation in performance is inevitable by proving a lower bound of I/Os for priority queues with DecreaseKeys. In this paper we tighten the gap between the lower bound and the upper bound by proposing a new priority queue which supports the DecreaseKey operation and has an expected amortized I/O complexity of . Our result improves the external memory priority queue with DecreaseKeys for the first time in over a decade, and also gives the fastest external memory single source shortest path algorithm.
BibTeX
@inproceedings{jiang2019faster,
  author = {Shunhua Jiang and Kasper Green Larsen},
  title = {{A Faster External Memory Priority Queue with DecreaseKeys}},
  booktitle = {SODA},
  year = {2019},
  url = {https://openreview.net/forum?id=yRISVjo5Jtw},
}
Figure