Efficient aggregation of ranked inputs

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

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

27 Citations (Scopus)


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. Adaptations of our algorithm for search variants (exact scores, on-line and Incremental search, top-k joins, other aggregate functions, etc.) are also provided. 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
Title of host publicationProceedings of the 22nd International Conference on Data Engineering, ICDE '06
Number of pages1
Publication statusPublished - 17 Oct 2006
Externally publishedYes
Event22nd International Conference on Data Engineering, ICDE '06 - Atlanta, GA, United States
Duration: 3 Apr 20067 Apr 2006


Conference22nd International Conference on Data Engineering, ICDE '06
Country/TerritoryUnited States
CityAtlanta, GA

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Efficient aggregation of ranked inputs'. Together they form a unique fingerprint.

Cite this