RAM-efficient external memory sorting

Lars Arge; Mikkel Thorup

doi:10.1007/978-3-642-45030-3_46

RAM-efficient external memory sorting

Lars Arge, Mikkel Thorup

Datalogisk Institut

3 Citationer (Scopus)

Abstract

In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we study algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation.

Originalsprog	Engelsk
Titel	Algorithms and Computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings
Redaktører	Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam
Antal sider	11
Forlag	Springer
Publikationsdato	2013
Sider	491-501
ISBN (Trykt)	978-3-642-45029-7
ISBN (Elektronisk)	978-3-642-45030-3
DOI	https://doi.org/10.1007/978-3-642-45030-3_46
Status	Udgivet - 2013
Begivenhed	24th International Symposium on Algorithms and Computation - Hong Kong, Kina Varighed: 16 dec. 2013 → 18 dec. 2013 Konferencens nummer: 24

Konference

Konference	24th International Symposium on Algorithms and Computation
Nummer	24
Land/Område	Kina
By	Hong Kong
Periode	16/12/2013 → 18/12/2013

Navn	Lecture notes in computer science
Vol/bind	8283
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-642-45030-3_46

Citationsformater

RAM-efficient external memory sorting. / Arge, Lars; Thorup, Mikkel.

Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. red. / Leizhen Cai; Siu-Wing Cheng; Tak-Wah Lam. Springer, 2013. s. 491-501 (Lecture notes in computer science, Bind 8283).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Arge, L & Thorup, M 2013, RAM-efficient external memory sorting. i L Cai, S-W Cheng & T-W Lam (red), Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. Springer, Lecture notes in computer science, bind 8283, s. 491-501, 24th International Symposium on Algorithms and Computation, Hong Kong, Kina, 16/12/2013. https://doi.org/10.1007/978-3-642-45030-3_46

@inproceedings{9cfc872517e54dd280870b16f960a809,

title = "RAM-efficient external memory sorting",

abstract = "In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we study algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation.",

author = "Lars Arge and Mikkel Thorup",

year = "2013",

doi = "10.1007/978-3-642-45030-3_46",

language = "English",

isbn = "978-3-642-45029-7",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "491--501",

editor = "Leizhen Cai and Siu-Wing Cheng and Tak-Wah Lam",

booktitle = "Algorithms and Computation",

note = "24th International Symposium on Algorithms and Computation, ISAAC 2013 ; Conference date: 16-12-2013 Through 18-12-2013",

}

TY - GEN

T1 - RAM-efficient external memory sorting

AU - Arge, Lars

AU - Thorup, Mikkel

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we study algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation.

AB - In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we study algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation.

U2 - 10.1007/978-3-642-45030-3_46

DO - 10.1007/978-3-642-45030-3_46

M3 - Article in proceedings

SN - 978-3-642-45029-7

T3 - Lecture notes in computer science

SP - 491

EP - 501

BT - Algorithms and Computation

A2 - Cai, Leizhen

A2 - Cheng, Siu-Wing

A2 - Lam, Tak-Wah

PB - Springer

T2 - 24th International Symposium on Algorithms and Computation

Y2 - 16 December 2013 through 18 December 2013

ER -

RAM-efficient external memory sorting

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater