A faster external memory priority queue with DecreaseKeys

DOI10.1137/1.9781611975482.81MaRDI QIDQ5236265zbMATH OpenOpenAlexFDO

Authors Shunhua Jiang, Kasper Green Larsen

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.07598

Mathematics Subject Classification ID

Data structures (68P05)

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(frac1BlogfracNB)$ 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(frac1BlogfracNB/logfracMB)$ I/Os. A recent result shows that a degradation in performance is inevitable by proving a lower bound of $Omega(frac1BlogB/loglogN)$ 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(frac1BlogfracNB/loglogN)$. 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.

Recommendations

• DecreaseKeys are expensive for external memory priority queues
• Worst-case efficient external-memory priority queues
• Equivalence between priority queues and sorting in external memory
• An experimental study of priority queues in external memory
• scientific article; zbMATH DE number 871900

Cited in

(9)

• Equivalence between priority queues and sorting in external memory
• DecreaseKeys are expensive for external memory priority queues
• Worst-case efficient external-memory priority queues
• External memory priority queues with decrease-key and applications to graph algorithms
• Lower bounds for external memory integer sorting via network coding
• An experimental study of priority queues in external memory
• Lazy B-trees
• External-memory priority queues with optimal insertions
• Support optimality and adaptive cuckoo filters

This page was built for publication: A faster external memory priority queue with DecreaseKeys

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236265)