DecreaseKeys are expensive for external memory priority queues

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


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) lgM/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) lg2 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 Ω((N/B) lglgN 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.

Original languageEnglish
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
Number of pages13
VolumePart F128415
Place of publicationNew York, NY
PublisherAssociation for Computing Machinery
Publication year19 Jun 2017
ISBN (Electronic)9781450345286
Publication statusPublished - 19 Jun 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: 19 Jun 201723 Jun 2017


Conference49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT)

    Research areas

  • Communication complexity, External memory, Lower bound, Priority queues

See relations at Aarhus University Citationformats

ID: 118423925