research-article

DecreaseKeys are expensive for external memory priority queues

Authors:

Kasper Eenberg,

Kasper Green Larsen,

Huacheng YuAuthors Info & Claims

STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

Pages 1081 - 1093

https://doi.org/10.1145/3055399.3055437

Published: 19 June 2017 Publication History

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)lg_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) lg₂ 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) lg_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.

Supplementary Material

MP4 File (d4_sc_t1.mp4)

Download
135.17 MB

References

[1]

A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31:1116–1127, 1988.

Digital Library

[2]

G. S. Brodal. Worst-case efficient priority queues. In Proc. 7th ACM/SIAM Symposium on Discrete Algorithms, SODA ’96, pages 52–58, 1996.

Digital Library

[3]

G. S. Brodal and R. Fagerberg. Lower bounds for external memory dictionaries. In Proc. 14th ACM/SIAM Symposium on Discrete Algorithms, SODA ’03, pages 546–554, 2003.

Digital Library

[4]

J. Brody, A. Chakrabarti, R. Kondapally, D. P. Woodruff, and G. Yaroslavtsev. Beyond set disjointness: The communication complexity of finding the intersection. In Proc. 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14, pages 106–113, 2014.

Digital Library

[5]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, Mass., 1990.

Digital Library

[6]

R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. Heaps and heapsort on secondary storage. Theoretical Computer Science, 220(2):345–362, June 1999.

Digital Library

[7]

M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596–615, July 1987.

Digital Library

[8]

Y. Han. Deterministic sorting in o(nlog log n) time and linear space. In Proc. 34th ACM Symposium on Theory of Computation, STOC ’02, pages 602–608, 2002.

Digital Library

[9]

Y. Han and M. Thorup. Integer sorting in O (n lg lg n) expected time and linear space. In Proc. 43rd IEEE Symposium on Foundations of Computer Science, pages 135–144, 2002.

Digital Library

[10]

J. Iacono and M. P ˇ atraşcu. Using hashing to solve the dictionary problem (in external memory). In Proc. 23rd ACM/SIAM Symposium on Discrete Algorithms, pages 570–582, 2012.

Digital Library

[11]

V. Kumar and E. J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In Proc. 8th IEEE Symposium on Parallel and Distributed Processing, SPDP ’96, pages 169–, 1996.

Digital Library

[12]

U. Meyer and N. Zeh. I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths, pages 540–551. 2006.

Digital Library

[13]

P. Miltersen, N. Nisan, S. Safra, and A. Wigderson. On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57(1):37–49, 1998.

Digital Library

[14]

M. Thorup. Integer priority queues with decrease key in constant time and the single source shortest paths problem. Journal of Computer and System Sciences, 69(3):330–353, 2004.

Digital Library

[15]

M. Thorup. Equivalence between priority queues and sorting. Journal of the ACM, 54(6), Dec. 2007.

Digital Library

[16]

E. Verbin and Q. Zhang. The limits of buffering: a tight lower bound for dynamic membership in the external memory model. In Proc. 42nd ACM Symposium on Theory of Computation, pages 447–456, 2010.

Digital Library

[17]

Z. Wei and K. Yi. Equivalence between priority queues and sorting in external memory. In Proc. 22nd European Symposium on Algorithms, pages 830–841, 2014.

[18]

A. C.-C. Yao. Should tables be sorted? Journal of the ACM, 28(3):615–628, 1981.

Digital Library

[19]

K. Yi and Q. Zhang. On the cell probe complexity of dynamic membership. In Proc. 21st ACM/SIAM Symposium on Discrete Algorithms, pages 123–133, 2010.

Digital Library

Cited By

Jafargholi ZLarsen KSimkin MMarx D(2021)Optimal oblivious priority queuesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458205(2366-2383)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458205
Farhadi AHajiaghayi MLarsen KShi E(2021)Lower Bounds for External Memory Integer Sorting via Network CodingSIAM Journal on Computing10.1137/20M132188752:2(STOC19-87-STOC19-111)Online publication date: 30-Sep-2021
https://doi.org/10.1137/20M1321887
Jacob RLarsen KNielsen JChan T(2019)Lower bounds for oblivious data structuresProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310584(2439-2447)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310584
Show More Cited By

Index Terms

DecreaseKeys are expensive for external memory priority queues
1. Theory of computation
  1. Computational complexity and cryptography
    1. Communication complexity
  2. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Cell probe models and lower bounds

Recommendations

(N,n)-preemptive priority queues

In this paper, we propose a new priority discipline, called the (N,n)-preemptive priority discipline. Under this discipline, the preemption of the service of a low-class customer is determined by two thresholds N and n of the queue length of high-class ...
On priority queues with impatient customers

In this paper, we study three different problems where one class of customers is given priority over the other class. In the first problem, a single server receives two classes of customers with general service time requirements and follows a preemptive-...
Melding priority queues

We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) amortized time, where n is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

June 2017

1268 pages

ISBN:9781450345286

DOI:10.1145/3055399

General Chairs:
Hamed Hatami
McGill University
,
Pierre McKenzie
Université de Montréal
,
Program Chair:
Valerie King
University of Victoria

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '17

Sponsor:

SIGACT

STOC '17: Symposium on Theory of Computing

June 19 - 23, 2017

Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
53
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jafargholi ZLarsen KSimkin MMarx D(2021)Optimal oblivious priority queuesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458205(2366-2383)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458205
Farhadi AHajiaghayi MLarsen KShi E(2021)Lower Bounds for External Memory Integer Sorting via Network CodingSIAM Journal on Computing10.1137/20M132188752:2(STOC19-87-STOC19-111)Online publication date: 30-Sep-2021
https://doi.org/10.1137/20M1321887
Jacob RLarsen KNielsen JChan T(2019)Lower bounds for oblivious data structuresProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310584(2439-2447)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310584
Jiang SLarsen KChan T(2019)A faster external memory priority queue with DecreaseKeysProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310516(1331-1343)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310516
Farhadi AHajiaghayi MLarsen KShi ECharikar MCohen E(2019)Lower bounds for external memory integer sorting via network codingProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316337(997-1008)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316337
Chowdhury RRamachandran V(2018)Cache-Oblivious Buffer Heap and Cache-Efficient Computation of Shortest Paths in GraphsACM Transactions on Algorithms10.1145/314717214:1(1-33)Online publication date: 3-Jan-2018
https://dl.acm.org/doi/10.1145/3147172

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents