A Faster External Memory Priority Queue with DecreaseKeys

Shunhua Jiang, Kasper Green Larsen

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 $O(\frac{1}{B}\log \frac{N}{B})$ 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 $O(\frac{1}{B}\log \frac{N}{B}/ \log \frac{M}{B})$ I/Os. A recent result shows that a degradation in performance is inevitable by proving a lower bound of $\Omega(\frac{1}{B}\log B/\log\log N)$ 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 $O(\frac{1}{B}\log \frac{N}{B}/\log\log N)$. 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},
}

Loading related content...

Figure