DecreaseKeys are expensive for external memory priority queues

DOI10.1145/3055399.3055437zbMATH Open1369.68170arXiv1611.00911OpenAlexW2546455469MaRDI QIDQ4978049FDOQ4978049

Huacheng Yu, Kasper Green Larsen, Kasper Eenberg

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be supported, one can design a comparison-based priority queue performing $O((N/B)l{g}_{M/B}N)$ I/Os over a sequence of $N$ operations, where $B$ is the disk block size in number of words and $M$ is the main memory size in number of words. This matches the lower bound for comparison-based sorting and is hence optimal for comparison-based priority queues. However, if we also need to support DecreaseKeys, the performance of the best known priority queue is only $O((N/B)l{g}_{2}N)$ I/Os. The big open question is whether a degradation in performance really is necessary. We answer this question affirmatively by proving a lower bound of $Omega((N/B)l{g}_{lgN}B)$ I/Os for processing a sequence of $N$ intermixed Insert, ExtraxtMin and DecreaseKey operations. Our lower bound is proved in the cell probe model and thus holds also for non-comparison-based priority queues.

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

zbMATH Keywords

lower boundcommunication complexityexternal memorypriority queues

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (1)

• Lower Bounds for External Memory Integer Sorting via Network Coding

This page was built for publication: DecreaseKeys are expensive for external memory priority queues

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