TY - GEN
T1 - Efficient quantile retrieval on multi-dimensional data
AU - Yiu, Man Lung
AU - Mamoulis, Nikos
AU - Tao, Yufei
PY - 2006/7/10
Y1 - 2006/7/10
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.
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.
UR - http://www.scopus.com/inward/record.url?scp=33745630648&partnerID=8YFLogxK
U2 - 10.1007/11687238_13
DO - 10.1007/11687238_13
M3 - Conference article published in proceeding or book
SN - 3540329609
SN - 9783540329602
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 -