Orthogonal range queries in OLAP

Chung Keung Poon

doi:10.1007/3-540-44503-x_23

Orthogonal range queries in OLAP

Chung Keung Poon

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

6 Citations (Scopus)

Abstract

We study the problem of pre-computing auxillary information to support on-line range queries for the sum and max functions on a datacube. For a d-dimensional datacube with size n in each dimension, we propose a data structure for range max queries with O((4L)^d) query time and O((12L²n^1/Lγ(n))^d) update time where Lε{1,….,log n} is a user-controlled parameter and Y(n) is a slow-growing function. (For example, γ(n) ≤log* n and γ(2⁴¹¹⁰) = 3.) The data structure uses O((6nγ(n))^d) storage and can be initialized in time linear to its size. There are three major techniques employed in designing the data structure, namely, a technique for trading query and update times, a technique for trading query time and storage and a technique for extending 1-dimensional data structures to d-dimensional ones. Our techniques are also applicable to range queries over any semi-group and group operation, such as min, sum and count. © Springer-Verlag Berlin Heidelberg 2001

Original language	English
Title of host publication	Database Theory - ICDT 2001 - 8th International Conference, Proceedings
Publisher	Springer Verlag
Pages	361-374
Volume	1973
ISBN (Print)	9783540414568
DOIs	https://doi.org/10.1007/3-540-44503-x_23
Publication status	Published - 2001
Event	8th International Conference on Database Theory, ICDT 2001 - London, United Kingdom Duration: 4 Jan 2001 → 6 Jan 2001

Publication series

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

Conference

Conference	8th International Conference on Database Theory, ICDT 2001
Place	United Kingdom
City	London
Period	4/01/01 → 6/01/01

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

This research was fully supported by a grant from the Research Grants Council of the Hong Kong SAR, China [Project No. 9040314 (RGC Ref. No. CityU 1159/97E)].

RGC Funding Information

RGC-funded

Access Output

10.1007/3-540-44503-x_23

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{ac8da10b6661484f8461a126b31b07f4,

title = "Orthogonal range queries in OLAP",

abstract = "We study the problem of pre-computing auxillary information to support on-line range queries for the sum and max functions on a datacube. For a d-dimensional datacube with size n in each dimension, we propose a data structure for range max queries with O((4L)d) query time and O((12L2n1/Lγ(n))d) update time where Lε{1,….,log n} is a user-controlled parameter and Y(n) is a slow-growing function. (For example, γ(n) ≤log* n and γ(24110) = 3.) The data structure uses O((6nγ(n))d) storage and can be initialized in time linear to its size. There are three major techniques employed in designing the data structure, namely, a technique for trading query and update times, a technique for trading query time and storage and a technique for extending 1-dimensional data structures to d-dimensional ones. Our techniques are also applicable to range queries over any semi-group and group operation, such as min, sum and count. {\textcopyright} Springer-Verlag Berlin Heidelberg 2001",

author = "Poon, {Chung Keung}",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; 8th International Conference on Database Theory, ICDT 2001 ; Conference date: 04-01-2001 Through 06-01-2001",

year = "2001",

doi = "10.1007/3-540-44503-x_23",

language = "English",

isbn = "9783540414568",

volume = "1973",

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

publisher = "Springer Verlag",

pages = "361--374",

booktitle = "Database Theory - ICDT 2001 - 8th International Conference, Proceedings",

address = "Germany",

}

Poon, CK 2001, Orthogonal range queries in OLAP. in Database Theory - ICDT 2001 - 8th International Conference, Proceedings. vol. 1973, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1973, Springer Verlag, pp. 361-374, 8th International Conference on Database Theory, ICDT 2001, London, United Kingdom, 4/01/01. https://doi.org/10.1007/3-540-44503-x_23

Orthogonal range queries in OLAP. / Poon, Chung Keung.
Database Theory - ICDT 2001 - 8th International Conference, Proceedings. Vol. 1973 Springer Verlag, 2001. p. 361-374 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1973).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Orthogonal range queries in OLAP

AU - Poon, Chung Keung

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2001

Y1 - 2001

N2 - We study the problem of pre-computing auxillary information to support on-line range queries for the sum and max functions on a datacube. For a d-dimensional datacube with size n in each dimension, we propose a data structure for range max queries with O((4L)d) query time and O((12L2n1/Lγ(n))d) update time where Lε{1,….,log n} is a user-controlled parameter and Y(n) is a slow-growing function. (For example, γ(n) ≤log* n and γ(24110) = 3.) The data structure uses O((6nγ(n))d) storage and can be initialized in time linear to its size. There are three major techniques employed in designing the data structure, namely, a technique for trading query and update times, a technique for trading query time and storage and a technique for extending 1-dimensional data structures to d-dimensional ones. Our techniques are also applicable to range queries over any semi-group and group operation, such as min, sum and count. © Springer-Verlag Berlin Heidelberg 2001

AB - We study the problem of pre-computing auxillary information to support on-line range queries for the sum and max functions on a datacube. For a d-dimensional datacube with size n in each dimension, we propose a data structure for range max queries with O((4L)d) query time and O((12L2n1/Lγ(n))d) update time where Lε{1,….,log n} is a user-controlled parameter and Y(n) is a slow-growing function. (For example, γ(n) ≤log* n and γ(24110) = 3.) The data structure uses O((6nγ(n))d) storage and can be initialized in time linear to its size. There are three major techniques employed in designing the data structure, namely, a technique for trading query and update times, a technique for trading query time and storage and a technique for extending 1-dimensional data structures to d-dimensional ones. Our techniques are also applicable to range queries over any semi-group and group operation, such as min, sum and count. © Springer-Verlag Berlin Heidelberg 2001

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84949476327&origin=recordpage

U2 - 10.1007/3-540-44503-x_23

DO - 10.1007/3-540-44503-x_23

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783540414568

VL - 1973

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

SP - 361

EP - 374

BT - Database Theory - ICDT 2001 - 8th International Conference, Proceedings

PB - Springer Verlag

T2 - 8th International Conference on Database Theory, ICDT 2001

Y2 - 4 January 2001 through 6 January 2001

ER -

Orthogonal range queries in OLAP

Abstract

Publication series

Conference

Bibliographical note

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this