License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.60
URN: urn:nbn:de:0030-drops-111817
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11181/
Iacono, John ;
Jacob, Riko ;
Tsakalidis, Konstantinos
External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms
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.
BibTeX - Entry
@InProceedings{iacono_et_al:LIPIcs:2019:11181,
author = {John Iacono and Riko Jacob and Konstantinos Tsakalidis},
title = {{External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {60:1--60:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11181},
URN = {urn:nbn:de:0030-drops-111817},
doi = {10.4230/LIPIcs.ESA.2019.60},
annote = {Keywords: priority queues, external memory, graph algorithms, shortest paths, depth-first search, breadth-first search}
}
|
Keywords: |
|
priority queues, external memory, graph algorithms, shortest paths, depth-first search, breadth-first search |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
