publication . Conference object . Contribution for newspaper or weekly magazine . Preprint . 2017

DecreaseKeys are expensive for external memory priority queues

Kasper Green Larsen;
  • Published: 19 Jun 2017
Abstract
<p>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<sub>M/B</sub> 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<sub>2</sub> N) I...
Subjects
free text keywords: Communication complexity, External memory, Lower bound, Priority queues, Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Double-ended priority queue, Discrete mathematics, Cell-probe model, Sorting, Auxiliary memory, Combinatorics, Data structure, Computer science, Priority queue, Upper and lower bounds
Related Organizations
Funded by
NSF| AF: Large: Collaborative Research: Exploiting Duality between Algorithms and Complexity
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1212372
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
19 references, page 1 of 2

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

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

[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. [OpenAIRE]

[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.

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

[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. [OpenAIRE]

[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.

[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.

[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. [OpenAIRE]

[10] J. Iacono and M. Paˇtra¸scu. Using hashing to solve the dictionary problem (in external memory). In Proc. 23rd ACM/SIAM Symposium on Discrete Algorithms, pages 570-582, 2012.

[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.

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

[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. [OpenAIRE]

[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. [OpenAIRE]

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

19 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Conference object . Contribution for newspaper or weekly magazine . Preprint . 2017

DecreaseKeys are expensive for external memory priority queues

Kasper Green Larsen;