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.
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: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3051856 |