Progressive and selective merge: Computing top-k with ad-hoc ranking functions

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The family of threshold algorithm (ie, TA) has been widely studied for efficiently computing top-k queries. TA uses a sort-merge framework that assumes data lists are pre-sorted, and the ranking functions are monotone. However, in many database applications, attribute values are indexed by tree-structured indices (eg, B-tree, R-tree), and the ranking functions are not necessarily monotone. To answer top-k queries with ad-hoc ranking functions, this paper studies anindex-merge paradigm that performs progressive search over the space of joint states composed by multiple index nodes. We address two challenges for efficient query processing. First, to minimize the search complexity, we present a double-heap algorithm which supports not only progressive state search but also progressive state generation. Second, to avoid unnecessary disk access, we characterize a type of "empty-state" that does not contribute to the final results, and propose a new materialization model, join-signature, to prune empty-states. Our performance study shows that the proposed method achieves one order of magnitude speed-up over baseline solutions.

Original languageEnglish (US)
Title of host publicationSIGMOD 2007
Subtitle of host publicationProceedings of the ACM SIGMOD International Conference on Management of Data
Pages103-114
Number of pages12
DOIs
StatePublished - Oct 30 2007
EventSIGMOD 2007: ACM SIGMOD International Conference on Management of Data - Beijing, China
Duration: Jun 12 2007Jun 14 2007

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Other

OtherSIGMOD 2007: ACM SIGMOD International Conference on Management of Data
CountryChina
CityBeijing
Period6/12/076/14/07

Keywords

  • Progressive merge
  • Selective merge
  • Top-k query

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'Progressive and selective merge: Computing top-k with ad-hoc ranking functions'. Together they form a unique fingerprint.

Cite this