Efficient quantile retrieval on multi-dimensional data

Man Lung Yiu, Nikos Mamoulis, Yufei Tao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

3 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings
Number of pages19
Publication statusPublished - 10 Jul 2006
Externally publishedYes
Event10th International Conference on Extending Database Technology, EDBT 2006 - Munich, Germany
Duration: 26 Mar 200631 Mar 2006

Publication series

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


Conference10th International Conference on Extending Database Technology, EDBT 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient quantile retrieval on multi-dimensional data'. Together they form a unique fingerprint.

Cite this