Efficient quantile retrieval on multi-dimensional data

Man Lung Yiu; Nikos Mamoulis; Yufei Tao

doi:10.1007/11687238_13

Efficient quantile retrieval on multi-dimensional data

Man Lung Yiu
, Nikos Mamoulis
, Yufei Tao

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

3 Citations (Scopus)

Abstract

Given a set of N multi-dimensional points, we study the computation of phi;-quantiles according to a ranking function F, which is provided by the user at runtime. Specifically, F computes a score based on the coordinates of each point; our objective is to report the object whose score is the φN-th smallest in the dataset. φ-quantiles provide a succinct summary about the F-distribution of the underlying data, which is useful for online decision support, data mining, selectivity estimation, query optimization, etc. Assuming that the dataset is indexed by a spatial access method, we propose several algorithms for retrieving a quantile efficiently. Analytical and experimental results demonstrate that a branch-and-bound method is highly effective in practice, outperforming alternative approaches by a significant factor. © Springer-Verlag Berlin Heidelberg 2006.

Original language	English
Title of host publication	Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings
Pages	167-185
Volume	3896 LNCS
DOIs	https://doi.org/10.1007/11687238_13
Publication status	Published - 2006
Externally published	Yes
Event	10th International Conference on Extending Database Technology, EDBT 2006 - Munich, Germany Duration: 26 Mar 2006 → 31 Mar 2006

Publication series

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

Conference

Conference	10th International Conference on Extending Database Technology, EDBT 2006
Place	Germany
City	Munich
Period	26/03/06 → 31/03/06

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

Work supported by grants HKU 7380/02E and CityU 1163/04E from Hong Kong RGC, and SRGgrant (Project NO: 7001843) from City University of Hong Kong.

RGC Funding Information

RGC-funded

Access Output

10.1007/11687238_13

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Yiu, M. L., Mamoulis, N., & Tao, Y. (2006). Efficient quantile retrieval on multi-dimensional data. In Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings (Vol. 3896 LNCS, pp. 167-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3896 LNCS). https://doi.org/10.1007/11687238_13

Yiu, Man Lung ; Mamoulis, Nikos ; Tao, Yufei. / Efficient quantile retrieval on multi-dimensional data. Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings. Vol. 3896 LNCS 2006. pp. 167-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4ca6e399acb84ef285294afe19c83400,

title = "Efficient quantile retrieval on multi-dimensional data",

abstract = "Given a set of N multi-dimensional points, we study the computation of phi;-quantiles according to a ranking function F, which is provided by the user at runtime. Specifically, F computes a score based on the coordinates of each point; our objective is to report the object whose score is the φN-th smallest in the dataset. φ-quantiles provide a succinct summary about the F-distribution of the underlying data, which is useful for online decision support, data mining, selectivity estimation, query optimization, etc. Assuming that the dataset is indexed by a spatial access method, we propose several algorithms for retrieving a quantile efficiently. Analytical and experimental results demonstrate that a branch-and-bound method is highly effective in practice, outperforming alternative approaches by a significant factor. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.",

author = "Yiu, \{Man Lung\} and Nikos Mamoulis and Yufei Tao",

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].; 10th International Conference on Extending Database Technology, EDBT 2006 ; Conference date: 26-03-2006 Through 31-03-2006",

year = "2006",

doi = "10.1007/11687238\_13",

language = "English",

isbn = "3540329609",

volume = "3896 LNCS",

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

pages = "167--185",

booktitle = "Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings",

}

Yiu, ML, Mamoulis, N & Tao, Y 2006, Efficient quantile retrieval on multi-dimensional data. in Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings. vol. 3896 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3896 LNCS, pp. 167-185, 10th International Conference on Extending Database Technology, EDBT 2006, Munich, Germany, 26/03/06. https://doi.org/10.1007/11687238_13

Efficient quantile retrieval on multi-dimensional data. / Yiu, Man Lung; Mamoulis, Nikos; Tao, Yufei.
Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings. Vol. 3896 LNCS 2006. p. 167-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3896 LNCS).

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

TY - GEN

T1 - Efficient quantile retrieval on multi-dimensional data

AU - Yiu, Man Lung

AU - Mamoulis, Nikos

AU - Tao, Yufei

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 - 2006

Y1 - 2006

N2 - Given a set of N multi-dimensional points, we study the computation of phi;-quantiles according to a ranking function F, which is provided by the user at runtime. Specifically, F computes a score based on the coordinates of each point; our objective is to report the object whose score is the φN-th smallest in the dataset. φ-quantiles provide a succinct summary about the F-distribution of the underlying data, which is useful for online decision support, data mining, selectivity estimation, query optimization, etc. Assuming that the dataset is indexed by a spatial access method, we propose several algorithms for retrieving a quantile efficiently. Analytical and experimental results demonstrate that a branch-and-bound method is highly effective in practice, outperforming alternative approaches by a significant factor. © Springer-Verlag Berlin Heidelberg 2006.

AB - Given a set of N multi-dimensional points, we study the computation of phi;-quantiles according to a ranking function F, which is provided by the user at runtime. Specifically, F computes a score based on the coordinates of each point; our objective is to report the object whose score is the φN-th smallest in the dataset. φ-quantiles provide a succinct summary about the F-distribution of the underlying data, which is useful for online decision support, data mining, selectivity estimation, query optimization, etc. Assuming that the dataset is indexed by a spatial access method, we propose several algorithms for retrieving a quantile efficiently. Analytical and experimental results demonstrate that a branch-and-bound method is highly effective in practice, outperforming alternative approaches by a significant factor. © Springer-Verlag Berlin Heidelberg 2006.

UR - https://www.scopus.com/pages/publications/33745630648

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

U2 - 10.1007/11687238_13

DO - 10.1007/11687238_13

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

SN - 3540329609

SN - 9783540329602

VL - 3896 LNCS

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

SP - 167

EP - 185

BT - Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings

T2 - 10th International Conference on Extending Database Technology, EDBT 2006

Y2 - 26 March 2006 through 31 March 2006

ER -

Yiu ML, Mamoulis N, Tao Y. Efficient quantile retrieval on multi-dimensional data. In Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings. Vol. 3896 LNCS. 2006. p. 167-185. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11687238_13

Efficient quantile retrieval on multi-dimensional data

Abstract

Publication series

Conference

Bibliographical note

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this