DecreaseKeys are Expensive for External Memory Priority Queues

Preprint, Contribution for newspaper or weekly magazine English OPEN
Eenberg, Kasper ; Larsen, Kasper Green ; Yu, Huacheng (2016)
  • Publisher: Association for Computing Machinery
  • Related identifiers: doi: 10.1145/3055399.3055437
  • Subject: Computer Science - Data Structures and Algorithms | Computer Science - Computational Complexity | Priority queues | Lower bound | Communication complexity | External memory

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)... View more
  • References (19)
    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.

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

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

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

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

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

  • Metrics
    No metrics available
Share - Bookmark