External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms

Iacono, John, Jacob, Riko and Tsakalidis, Konstantinos ORCID: 0000-0001-6470-9332 (2019) External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms. 27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019), 144.

Access the full-text of this item by clicking on the Open Access link.

Text 1903.03147v2.pdf - Submitted version Download (524kB) | Preview

Abstract

We present priority queues in the cache-oblivious external memory model with block size $B$ and main memory size $M$ that support on $N$ elements, operation \textsc{UPDATE} (combination of \textsc{INSERT} and \textsc{DECREASEKEY}) in $O \left(\frac{1}{B}\log_{\frac{\lambda}{B}} \frac{N}{B}\right)$ amortized I/Os and operations \textsc{EXTRACT-MIN} and \textsc{DELETE} in $O \left(\lceil \frac{\lambda^{\varepsilon}}{B} \log_{\frac{\lambda}{B}} \frac{N}{B} \rceil \log_{\frac{\lambda}{B}} \frac{N}{B}\right)$ amortized I/Os, using $O \left(\frac{N}{B}\log_{\frac{\lambda}{B}} \frac{N}{B}\right)$ blocks, for a user-defined parameter $\lambda \in [2, N ]$ and any real $\varepsilon \in (0,1)$. Our result improves upon previous I/O-efficient cache-oblivious and cache-aware priority queues [Chowdhury and Ramachandran, TALG 2018], [Brodal et al., SWAT 2004], [Kumar and Schwabe, SPDP 1996], [Arge et al., SICOMP 2007], [Fadel et al., TCS 1999]. We also present buffered repository trees that support on a multi-set of $N$ elements, operation \textsc{INSERT} in $O \left(\frac{1}{B}\log_{\frac{\lambda}{B}} \frac{N}{B}\right)$ I/Os and operation \textsc{EXTRACT} on $K$ extracted elements in $O \left(\frac{\lambda^{\varepsilon}}{B} \log_{\frac{\lambda}{B}} \frac{N}{B} + \frac{K}{B}\right)$ amortized I/Os, using $O \left(\frac{N}{B}\right)$ blocks, improving previous cache-aware and cache-oblivious results [Arge et al., SICOMP '07], [Buchsbaum et al., SODA '00]. In the cache-oblivious model, for $\lambda = O \left(E/V\right)$, we achieve $O \left(\frac{E}{B}\log_{\frac{E}{V B}} \frac{E}{B}\right)$ I/Os for single-source shortest paths, depth-first search and breadth-first search algorithms on massive directed dense graphs $(V,E)$. Our algorithms are I/O-optimal for $E/V = \Omega (M)$ (and in the cache-aware setting for $\lambda = O(M)$).

Item Type:	Article
Additional Information:	A preliminary version of this work is published in ESA 2019
Uncontrolled Keywords:	priority queues, external memory, graph algorithms, shortest paths, depth-first search, breadth-first search
Depositing User:	Symplectic Admin
Date Deposited:	15 Aug 2019 14:39
Last Modified:	19 Jan 2023 00:29
DOI:	10.4230/LIPIcs.ESA.2019.60
Open Access URL:	https://drops.dagstuhl.de/opus/volltexte/2019/1118...
Related URLs:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3051856