Efficient top-k aggregation of ranked inputs

Nikos Mamoulis, Man Lung Yiu, Kit Hung Cheng, David W. Cheung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

80 Citations (Scopus)

Abstract

A top-k query combines different rankings of the same set of objects and returns the k objects with the highest combined score according to an aggregate function. We bring to light some key observations, which impose two phases that any top-k algorithm, based on sorted accesses, should go through. Based on them, we propose a new algorithm, which is designed to minimize the number of object accesses, the computational cost, and the memory requirements of top-k search with monotone aggregate functions. We provide an analysis for its cost and show that it is always no worse than the baseline no random accesses algorithm in terms of computations, accesses, and memory required. As a side contribution, we perform a space analysis, which indicates the memory requirements of top-k algorithms that only perform sorted accesses. For the case, where the required space exceeds the available memory, we propose disk-based variants of our algorithm. We propose and optimize a multiway top-k join operator, with certain advantages over evaluation trees of binary top-k join operators. Finally, we define and study the computation of top-k cubes and the implementation of roll-up and drill-down operations in such cubes. Extensive experiments with synthetic and real data show that, compared to previous techniques, our method accesses fewer objects, while being orders of magnitude faster.
Original languageEnglish
Article number1272749
JournalACM Transactions on Database Systems
Volume32
Issue number3
DOIs
Publication statusPublished - 1 Aug 2007
Externally publishedYes

Keywords

  • Rank aggregation
  • Top-k queries

ASJC Scopus subject areas

  • Information Systems

Cite this