Gå til søgefeltetSpring over til navigationSpring til hovedindhold

External memory priority queues with decrease-key and applications to graph algorithms

Publikation:
Artikel i tidsskrift og konference artikel i tidsskrift
Konferenceartikel
Forskning
Peer-review

Open Access

Resume

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 Decrease-Key) in $O\left( \frac{1}{B}\log_{\frac{M}{B}} \frac{N}{B}\right)$ amortized I/Os and operations Extract-Min and Delete in $O\left( \lceil \frac{M^{\varepsilon}}{B} \log_{\frac{M}{B}} \frac{N}{B} \rceil \log_{\frac{M}{B}} \frac{N}{B}\right)$ amortized I/Os, for any real $\varepsilon \in \left(0,1\right)$, using $O\left( \frac{N}{B}\log_{\frac{M}{B}} \frac{N}{B}\right)$ blocks. Previous I/O-efficient priority queues either support these operations in $O\left(\frac{1}{B}\log_2 \frac{N}{B}\right)$ amortized I/Os [Kumar and Schwabe, SPDP '96] or support only operations Insert, Delete and Extract-Min in optimal $O\left( \frac{1}{B}\log_{\frac{M}{B}} \frac{N}{B}\right) $ amortized I/Os, however without supporting Decrease-Key [Fadel et al., TCS '99]. We also present buffered repository trees that support on a multi-set of $N$ elements, operation Insert in $O\left(\frac{1}{B}\log_{\frac{M}{B}} \frac{N}{B}\right)$ I/Os and operation Extract on $K$ extracted elements in $O\left( M^{\varepsilon}\log_{\frac{M}{B}} \frac{N}{B} + K/B\right)$ amortized I/Os, using $O \left(\frac{N}{B}\right)$ blocks. Previous results achieve $O\left(\frac{1}{B}\log_2 \frac{N}{B}\right)$ I/Os and $O\left( \log_2 \frac{N}{B} + \frac{K}{B}\right)$ I/Os, respectively [Buchsbaum et al., SODA '00]. Our results imply improved $O\left(\frac{E}{B}\log_{\frac{M}{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 $\left(V,E\right)$ with $E = \Omega \left( V^{1+\varepsilon}\right), \varepsilon > 0$ and $V = \Omega \left( M \right)$, which is equal to the I/O-optimal bound for sorting $E$ values in external memory.

Publikation information

Produktionstype

Publikation:
Artikel i tidsskrift og konference artikel i tidsskrift
Konferenceartikel
Forskning
Peer-review

Originalsprog

Engelsk

Artikelnummer

60

Sider fra-til (Antal sider)

Sider 60:1–60:14

Tidsskrift (Bind, Nummer)

Leibniz International Proceedings in Informatics

Publikationsmilepæle

  • Udgivet - 07/03/2019

Publikationsstatus

Udgivet - 07/03/2019

ISSN

1868-8969

Publikations IDer

  • Scopus: 85074817275

Metrikker

PlumX, åbner i en ny fane

Hentninger
5
Antal citationer
4

Relateret event

Titel

European Symposium on Algorithms

Begivenhedstype

Symposium

Grad af anerkendelse

International begivenhed

Dato

09/09/2019 - 11/09/2019

Lokation

GarchingMunichTyskland