A Faster External Memory Priority Queue with DecreaseKeys

Shunhua Jiang, Kasper Green Larsen

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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( B 1 log 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( B 1 log N B /log M B ) I/Os. A recent result shows that a degradation in performance is inevitable by proving a lower bound of Ω( B 1 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( B 1 log 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.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
EditorsTimothy M. Chan
Number of pages13
VolumePRDA19
PublisherSociety for Industrial and Applied Mathematics
Publication date2019
Pages1331-1343
ISBN (Electronic)978-1-61197-548-2
Publication statusPublished - 2019
EventThirtieth Annual ACM-SIAM Symposium on Discrete Algorithms - Westin San Diego , San Diego, United States
Duration: 6 Jan 20199 Jan 2019
Conference number: 30

Conference

ConferenceThirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
Number30
LocationWestin San Diego
Country/TerritoryUnited States
CitySan Diego
Period06/01/201909/01/2019

Fingerprint

Dive into the research topics of 'A Faster External Memory Priority Queue with DecreaseKeys'. Together they form a unique fingerprint.

Cite this