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)

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.
Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings
Pages167-185
Number of pages19
DOIs
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

Conference

Conference10th International Conference on Extending Database Technology, EDBT 2006
CountryGermany
CityMunich
Period26/03/0631/03/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this