Priority queues and sorting for read-only data

Tetsuo Asano; Amr Elmasry; Jyrki Katajainen

doi:10.1007/978-3-642-38236-9_4

Priority queues and sorting for read-only data

Tetsuo Asano, Amr Elmasry, Jyrki Katajainen

Datalogisk Institut

16 Citationer (Scopus)

91 Downloads (Pure)

Abstract

We revisit the random-access-machine model in which the input is given on a read-only random-access media, the output is to be produced to a write-only sequential-access media, and in addition there is a limited random-access workspace. The length of the input is N elements, the length of the output is limited by the computation itself, and the capacity of the workspace is O(S + w) bits, where S is a parameter specified by the user and w is the number of bits per machine word. We present a state-of-the-art priority queue-called an adjustable navigation pile-for this model. Under some reasonable assumptions, our priority queue supports minimum and insert in O(1) worst-case time and extract in O(N/S+lg S) worst-case time, where lg N ≤ S ≤ N/lg N. We also show how to use this data structure to simplify the existing optimal O(N ²/S + N lg S)-time sorting algorithm for this model.

Originalsprog	Engelsk
Titel	Theory and Applications of Models of Computation : 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings
Redaktører	T-H. Hubert Chan, Lap Chi Lau, Luca Trevisan
Antal sider	10
Forlag	Springer
Publikationsdato	2013
Sider	32-41
ISBN (Trykt)	978-3-642-38235-2
ISBN (Elektronisk)	978-3-642-38236-9
DOI	https://doi.org/10.1007/978-3-642-38236-9_4
Status	Udgivet - 2013
Begivenhed	10th International Conference on Theory and Applications of Models of Computation - Hong Kong, Kina Varighed: 20 maj 2013 → 22 maj 2013 Konferencens nummer: 10

Konference

Konference	10th International Conference on Theory and Applications of Models of Computation
Nummer	10
Land/Område	Kina
By	Hong Kong
Periode	20/05/2013 → 22/05/2013

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

Adgang til dokumentet

10.1007/978-3-642-38236-9_4

Priority queues and sorting for read-only dataAccepteret manuskript, 257 KBLicens: Andet

Citationsformater

Asano, T., Elmasry, A., & Katajainen, J. (2013). Priority queues and sorting for read-only data. I T-H. H. Chan, L. C. Lau, & L. Trevisan (red.), Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings (s. 32-41). Springer. Lecture notes in computer science Bind 7876 https://doi.org/10.1007/978-3-642-38236-9_4

Priority queues and sorting for read-only data. / Asano, Tetsuo; Elmasry, Amr; Katajainen, Jyrki.

Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. red. / T-H. Hubert Chan; Lap Chi Lau; Luca Trevisan. Springer, 2013. s. 32-41 (Lecture notes in computer science, Bind 7876).

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

Asano, T, Elmasry, A & Katajainen, J 2013, Priority queues and sorting for read-only data. i T-HH Chan, LC Lau & L Trevisan (red), Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. Springer, Lecture notes in computer science, bind 7876, s. 32-41, 10th International Conference on Theory and Applications of Models of Computation, Hong Kong, Kina, 20/05/2013. https://doi.org/10.1007/978-3-642-38236-9_4

@inproceedings{c106dad173514cc2b38069552b94058a,

title = "Priority queues and sorting for read-only data",

abstract = "We revisit the random-access-machine model in which the input is given on a read-only random-access media, the output is to be produced to a write-only sequential-access media, and in addition there is a limited random-access workspace. The length of the input is N elements, the length of the output is limited by the computation itself, and the capacity of the workspace is O(S + w) bits, where S is a parameter specified by the user and w is the number of bits per machine word. We present a state-of-the-art priority queue-called an adjustable navigation pile-for this model. Under some reasonable assumptions, our priority queue supports minimum and insert in O(1) worst-case time and extract in O(N/S+lg S) worst-case time, where lg N ≤ S ≤ N/lg N. We also show how to use this data structure to simplify the existing optimal O(N 2/S + N lg S)-time sorting algorithm for this model.",

author = "Tetsuo Asano and Amr Elmasry and Jyrki Katajainen",

year = "2013",

doi = "10.1007/978-3-642-38236-9_4",

language = "English",

isbn = "978-3-642-38235-2",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "32--41",

editor = "Chan, {T-H. Hubert} and Lau, {Lap Chi} and Luca Trevisan",

booktitle = "Theory and Applications of Models of Computation",

note = "10th International Conference on Theory and Applications of Models of Computation, TAMC 2013 ; Conference date: 20-05-2013 Through 22-05-2013",

}

TY - GEN

T1 - Priority queues and sorting for read-only data

AU - Asano, Tetsuo

AU - Elmasry, Amr

AU - Katajainen, Jyrki

N1 - Conference code: 10

PY - 2013

Y1 - 2013

N2 - We revisit the random-access-machine model in which the input is given on a read-only random-access media, the output is to be produced to a write-only sequential-access media, and in addition there is a limited random-access workspace. The length of the input is N elements, the length of the output is limited by the computation itself, and the capacity of the workspace is O(S + w) bits, where S is a parameter specified by the user and w is the number of bits per machine word. We present a state-of-the-art priority queue-called an adjustable navigation pile-for this model. Under some reasonable assumptions, our priority queue supports minimum and insert in O(1) worst-case time and extract in O(N/S+lg S) worst-case time, where lg N ≤ S ≤ N/lg N. We also show how to use this data structure to simplify the existing optimal O(N 2/S + N lg S)-time sorting algorithm for this model.

AB - We revisit the random-access-machine model in which the input is given on a read-only random-access media, the output is to be produced to a write-only sequential-access media, and in addition there is a limited random-access workspace. The length of the input is N elements, the length of the output is limited by the computation itself, and the capacity of the workspace is O(S + w) bits, where S is a parameter specified by the user and w is the number of bits per machine word. We present a state-of-the-art priority queue-called an adjustable navigation pile-for this model. Under some reasonable assumptions, our priority queue supports minimum and insert in O(1) worst-case time and extract in O(N/S+lg S) worst-case time, where lg N ≤ S ≤ N/lg N. We also show how to use this data structure to simplify the existing optimal O(N 2/S + N lg S)-time sorting algorithm for this model.

U2 - 10.1007/978-3-642-38236-9_4

DO - 10.1007/978-3-642-38236-9_4

M3 - Article in proceedings

SN - 978-3-642-38235-2

T3 - Lecture notes in computer science

SP - 32

EP - 41

BT - Theory and Applications of Models of Computation

A2 - Chan, T-H. Hubert

A2 - Lau, Lap Chi

A2 - Trevisan, Luca

PB - Springer

T2 - 10th International Conference on Theory and Applications of Models of Computation

Y2 - 20 May 2013 through 22 May 2013

ER -

Priority queues and sorting for read-only data

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater