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/Oefficient 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 multiset 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 singlesource shortest paths, depthfirst search and breadthfirst 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/Ooptimal 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 DecreaseKey and Applications to Graph Algorithms}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {60:160:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11181},
URN = {urn:nbn:de:0030drops111817},
doi = {10.4230/LIPIcs.ESA.2019.60},
annote = {Keywords: priority queues, external memory, graph algorithms, shortest paths, depthfirst search, breadthfirst search}
}
Keywords: 

priority queues, external memory, graph algorithms, shortest paths, depthfirst search, breadthfirst search 
Collection: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 