LIPIcs.ESA.2019.60.pdf
- Filesize: 0.49 MB
- 14 pages
Document
External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms
Authors
John Iacono 
,
Konstantinos Tsakalidis
-
Part of:
Volume:
27th Annual European Symposium on Algorithms (ESA 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-06
File
Document Identifiers
Author Details
Cite AsGet BibTex
John Iacono, Riko Jacob, and Konstantinos Tsakalidis. External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.60
https://doi.org/10.4230/LIPIcs.ESA.2019.60
Abstract
We present priority queues in the external memory model with block size B and main memory size M that support on N elements, operation Update (a combination of operations Insert and DecreaseKey) in O(1/Blog_{M/B} N/B) amortized I/Os and operations ExtractMin and Delete in O(ceil[(M^epsilon)/B log_{M/B} N/B] log_{M/B} N/B) amortized I/Os, for any real epsilon in (0,1), using O(N/Blog_{M/B} N/B) blocks. Previous I/O-efficient priority queues either support these operations in O(1/Blog_2 N/B) amortized I/Os [Kumar and Schwabe, SPDP '96] or support only operations Insert, Delete and ExtractMin in optimal O(1/Blog_{M/B} N/B) amortized I/Os, however without supporting DecreaseKey [Fadel et al., TCS '99].
We also present buffered repository trees that support on a multi-set of N elements, operation Insert in O(1/Blog_M/B N/B) I/Os and operation Extract on K extracted elements in O(M^{epsilon} log_M/B N/B + K/B) amortized I/Os, using O(N/B) blocks. Previous results achieve O(1/Blog_2 N/B) I/Os and O(log_2 N/B + K/B) I/Os, respectively [Buchsbaum et al., SODA '00].
Our results imply improved O(E/Blog_{M/B} E/B) I/Os for single-source shortest paths, depth-first search and breadth-first search algorithms on massive directed dense graphs (V,E) with E = Omega (V^(1+epsilon)), epsilon > 0 and V = Omega (M), which is equal to the I/O-optimal bound for sorting E values in external memory.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
- Theory of computation → Shortest paths
- Theory of computation → Data structures design and analysis
- Hardware → External storage
Keywords
- priority queues
- external memory
- graph algorithms
- shortest paths
- depth-first search
- breadth-first search
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alok Aggarwal and S. Vitter, Jeffrey. The Input/Output Complexity of Sorting and Related Problems. Commun. ACM, 31(9):1116-1127, September 1988. URL: https://doi.org/10.1145/48529.48535.
- Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland‐Minkley, and J. Ian Munro. An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms. SIAM Journal on Computing, 36(6):1672-1695, 2007. URL: https://doi.org/10.1137/S0097539703428324.
- Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time Bounds for Selection. J. Comput. Syst. Sci., 7(4):448-461, August 1973. URL: https://doi.org/10.1016/S0022-0000(73)80033-9.
- Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, and J. Ian Munro. Cache-oblivious Dynamic Dictionaries with Update/Query Tradeoffs. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 1448-1456, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1873601.1873718.
-
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, and Norbert Zeh. Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. In Torben Hagerup and Jyrki Katajainen, editors, Algorithm Theory - SWAT 2004, pages 480-492, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.
- Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, and Jeffery R. Westbrook. On External Memory Graph Traversal. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, pages 859-860, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=338219.338650.
- Rezaul A. Chowdhury and Vijaya Ramachandran. Cache-Oblivious Buffer Heap and Cache-Efficient Computation of Shortest Paths in Graphs. ACM Trans. Algorithms, 14(1):1:1-1:33, January 2018. URL: https://doi.org/10.1145/3147172.
- Alex Conway, Martín Farach-Colton, and Philip Shilane. Optimal Hashing in External Memory. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 39:1-39:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.39.
- Kasper Eenberg, Kasper Green Larsen, and Huacheng Yu. DecreaseKeys Are Expensive for External Memory Priority Queues. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1081-1093, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3055399.3055437.
- R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. Heaps and Heapsort on Secondary Storage. Theor. Comput. Sci., 220(2):345-362, June 1999. URL: https://doi.org/10.1016/S0304-3975(99)00006-7.
- Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. Cache-Oblivious Algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS '99, pages 285-, Washington, DC, USA, 1999. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=795665.796479.
- John Iacono and Mihai Pătraşcu. Using Hashing to Solve the Dictionary Problem. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 570-582, Philadelphia, PA, USA, 2012. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2095116.2095164.
- Shunhua Jiang and Kasper Green Larsen. A Faster External Memory Priority Queue with DecreaseKeys. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1331-1343. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.81.
- Vijay Kumar and Eric J. Schwabe. Improved Algorithms and Data Structures for Solving Graph Problems in External Memory. In Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), SPDP '96, pages 169-, Washington, DC, USA, 1996. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=829517.830723.
- Jeffrey Scott Vitter. External Memory Algorithms and Data Structures: Dealing with Massive Data. ACM Comput. Surv., 33(2):209-271, June 2001. URL: https://doi.org/10.1145/384192.384193.
-
Zhewei Wei and Ke Yi. Equivalence between Priority Queues and Sorting in External Memory. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014, pages 830-841, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.