Unit-time predecessor queries on massive data sets

Andrej Brodnik; John Iacono

doi:10.1007/978-3-642-17517-6_14

Unit-time predecessor queries on massive data sets

Andrej Brodnik, John Iacono

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

New data structures are presented for very fast predecessor queries on integer data sets stored on multiple disks. A structure is presented that supports predecessor queries in one disk seek performed in parallel over multiple disks, no matter how large the data set. For truly massive data sets, the space requirement of this structure approaches twice the space needed to simply store the data on disk. A second structure is presented that supports predecessor queries in the time it takes to perform two disk seeks, but has more moderate space requirements. Its space usage approaches the space needed to store the data on disk, and has manageable space requirements for smaller massive data sets.

Original language	English (US)
Title of host publication	Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages	133-144
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-17517-6_14
State	Published - 2010
Event	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: Dec 15 2010 → Dec 17 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6506 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Country/Territory	Korea, Republic of
City	Jeju Island
Period	12/15/10 → 12/17/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-17517-6_14

Cite this

Brodnik, A., & Iacono, J. (2010). Unit-time predecessor queries on massive data sets. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings (PART 1 ed., pp. 133-144). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6506 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-17517-6_14

Unit-time predecessor queries on massive data sets. / Brodnik, Andrej; Iacono, John.
Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 1. ed. 2010. p. 133-144 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6506 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Brodnik, A & Iacono, J 2010, Unit-time predecessor queries on massive data sets. in Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6506 LNCS, pp. 133-144, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 12/15/10. https://doi.org/10.1007/978-3-642-17517-6_14

@inproceedings{cfedb691404a45ff8a64a2e2acea46f4,

title = "Unit-time predecessor queries on massive data sets",

abstract = "New data structures are presented for very fast predecessor queries on integer data sets stored on multiple disks. A structure is presented that supports predecessor queries in one disk seek performed in parallel over multiple disks, no matter how large the data set. For truly massive data sets, the space requirement of this structure approaches twice the space needed to simply store the data on disk. A second structure is presented that supports predecessor queries in the time it takes to perform two disk seeks, but has more moderate space requirements. Its space usage approaches the space needed to store the data on disk, and has manageable space requirements for smaller massive data sets.",

author = "Andrej Brodnik and John Iacono",

note = "Funding Information: ★Research partially supported by NSF grants CCF-0430849, OISE-0334653, CCF- Funding Information: 1018370, and an Alfred P. Sloan fellowship, and by MADALGO—Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, Aarhus University.; 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",

year = "2010",

doi = "10.1007/978-3-642-17517-6_14",

language = "English (US)",

isbn = "3642175163",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "133--144",

booktitle = "Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings",

edition = "PART 1",

}

TY - GEN

T1 - Unit-time predecessor queries on massive data sets

AU - Brodnik, Andrej

AU - Iacono, John

N1 - Funding Information: ★Research partially supported by NSF grants CCF-0430849, OISE-0334653, CCF- Funding Information: 1018370, and an Alfred P. Sloan fellowship, and by MADALGO—Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, Aarhus University.

PY - 2010

Y1 - 2010

N2 - New data structures are presented for very fast predecessor queries on integer data sets stored on multiple disks. A structure is presented that supports predecessor queries in one disk seek performed in parallel over multiple disks, no matter how large the data set. For truly massive data sets, the space requirement of this structure approaches twice the space needed to simply store the data on disk. A second structure is presented that supports predecessor queries in the time it takes to perform two disk seeks, but has more moderate space requirements. Its space usage approaches the space needed to store the data on disk, and has manageable space requirements for smaller massive data sets.

AB - New data structures are presented for very fast predecessor queries on integer data sets stored on multiple disks. A structure is presented that supports predecessor queries in one disk seek performed in parallel over multiple disks, no matter how large the data set. For truly massive data sets, the space requirement of this structure approaches twice the space needed to simply store the data on disk. A second structure is presented that supports predecessor queries in the time it takes to perform two disk seeks, but has more moderate space requirements. Its space usage approaches the space needed to store the data on disk, and has manageable space requirements for smaller massive data sets.

UR - http://www.scopus.com/inward/record.url?scp=78650921936&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650921936&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17517-6_14

DO - 10.1007/978-3-642-17517-6_14

M3 - Conference contribution

AN - SCOPUS:78650921936

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 133

EP - 144

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -

Unit-time predecessor queries on massive data sets

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this