Multidimensional range selection

Timothy M. Chan; Gelin Zhou

doi:10.1007/978-3-662-48971-0_8

Multidimensional range selection

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

Abstract

We study the problem of supporting (orthogonal) range selection queries over a set of n points in constant-dimensional space. Under the standard word-RAM model with word size w = Ω(lg n), we present data structures that occupy O(n · (lg n/ lg lg n)^d−1) words of space and support d-dimensional range selection queries using O((lg n/ lg lg n)^d) query time. This improves the best known data structure by a factor of lg lg n in query time. To develop our data structures, we generalize the “parallel counting” technique of Brodal, Gfeller, Jørgensen, and Sanders (2011) for one-dimensional range selection to higher dimensions. As a byproduct, we design data structures to support d-dimensional range counting queries within O(n · (lg n/ lg w + 1)^d−2) words of space and O((lg n/ lg w + 1)^d−1) query time, for any word size w = Ω(lg n). This improves the best known result of JaJa, Mortensen, and Shi (2004) when lg w ≫ lg lg n.

Original language	English (US)
Title of host publication	Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings
Editors	Khaled Elbassioni, Kazuhisa Makino
Publisher	Springer
Pages	83-92
Number of pages	10
ISBN (Print)	9783662489703
DOIs	https://doi.org/10.1007/978-3-662-48971-0_8
State	Published - 2015
Externally published	Yes
Event	26th International Symposium on Algorithms and Computation, ISAAC 2015 - Nagoya, Japan Duration: Dec 9 2015 → Dec 11 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9472
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	26th International Symposium on Algorithms and Computation, ISAAC 2015
Country/Territory	Japan
City	Nagoya
Period	12/9/15 → 12/11/15

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-662-48971-0_8

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M., & Zhou, G. (2015). Multidimensional range selection. In K. Elbassioni, & K. Makino (Eds.), Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings (pp. 83-92). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9472). Springer. https://doi.org/10.1007/978-3-662-48971-0_8

Multidimensional range selection. / Chan, Timothy M.; Zhou, Gelin.
Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings. ed. / Khaled Elbassioni; Kazuhisa Makino. Springer, 2015. p. 83-92 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9472).

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

Chan, TM & Zhou, G 2015, Multidimensional range selection. in K Elbassioni & K Makino (eds), Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9472, Springer, pp. 83-92, 26th International Symposium on Algorithms and Computation, ISAAC 2015, Nagoya, Japan, 12/9/15. https://doi.org/10.1007/978-3-662-48971-0_8

@inproceedings{8f4a0d2c85c8485ebe4c2e4bd469761c,

title = "Multidimensional range selection",

abstract = "We study the problem of supporting (orthogonal) range selection queries over a set of n points in constant-dimensional space. Under the standard word-RAM model with word size w = Ω(lg n), we present data structures that occupy O(n · (lg n/ lg lg n)d−1) words of space and support d-dimensional range selection queries using O((lg n/ lg lg n)d) query time. This improves the best known data structure by a factor of lg lg n in query time. To develop our data structures, we generalize the “parallel counting” technique of Brodal, Gfeller, J{\o}rgensen, and Sanders (2011) for one-dimensional range selection to higher dimensions. As a byproduct, we design data structures to support d-dimensional range counting queries within O(n · (lg n/ lg w + 1)d−2) words of space and O((lg n/ lg w + 1)d−1) query time, for any word size w = Ω(lg n). This improves the best known result of JaJa, Mortensen, and Shi (2004) when lg w ≫ lg lg n.",

author = "Chan, {Timothy M.} and Gelin Zhou",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 26th International Symposium on Algorithms and Computation, ISAAC 2015 ; Conference date: 09-12-2015 Through 11-12-2015",

year = "2015",

doi = "10.1007/978-3-662-48971-0_8",

language = "English (US)",

isbn = "9783662489703",

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

publisher = "Springer",

pages = "83--92",

editor = "Khaled Elbassioni and Kazuhisa Makino",

booktitle = "Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Multidimensional range selection

AU - Chan, Timothy M.

AU - Zhou, Gelin

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - We study the problem of supporting (orthogonal) range selection queries over a set of n points in constant-dimensional space. Under the standard word-RAM model with word size w = Ω(lg n), we present data structures that occupy O(n · (lg n/ lg lg n)d−1) words of space and support d-dimensional range selection queries using O((lg n/ lg lg n)d) query time. This improves the best known data structure by a factor of lg lg n in query time. To develop our data structures, we generalize the “parallel counting” technique of Brodal, Gfeller, Jørgensen, and Sanders (2011) for one-dimensional range selection to higher dimensions. As a byproduct, we design data structures to support d-dimensional range counting queries within O(n · (lg n/ lg w + 1)d−2) words of space and O((lg n/ lg w + 1)d−1) query time, for any word size w = Ω(lg n). This improves the best known result of JaJa, Mortensen, and Shi (2004) when lg w ≫ lg lg n.

AB - We study the problem of supporting (orthogonal) range selection queries over a set of n points in constant-dimensional space. Under the standard word-RAM model with word size w = Ω(lg n), we present data structures that occupy O(n · (lg n/ lg lg n)d−1) words of space and support d-dimensional range selection queries using O((lg n/ lg lg n)d) query time. This improves the best known data structure by a factor of lg lg n in query time. To develop our data structures, we generalize the “parallel counting” technique of Brodal, Gfeller, Jørgensen, and Sanders (2011) for one-dimensional range selection to higher dimensions. As a byproduct, we design data structures to support d-dimensional range counting queries within O(n · (lg n/ lg w + 1)d−2) words of space and O((lg n/ lg w + 1)d−1) query time, for any word size w = Ω(lg n). This improves the best known result of JaJa, Mortensen, and Shi (2004) when lg w ≫ lg lg n.

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

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

U2 - 10.1007/978-3-662-48971-0_8

DO - 10.1007/978-3-662-48971-0_8

M3 - Conference contribution

AN - SCOPUS:84951936661

SN - 9783662489703

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

SP - 83

EP - 92

BT - Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings

A2 - Elbassioni, Khaled

A2 - Makino, Kazuhisa

PB - Springer

T2 - 26th International Symposium on Algorithms and Computation, ISAAC 2015

Y2 - 9 December 2015 through 11 December 2015

ER -

Multidimensional range selection

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this