Efficient Top-k Aggregation of Ranked Inputs
NIKOS MAMOULIS
University of Hong Kong
MAN LUNG YIU
Aalborg University
KIT HUNG CHENG
University of Hong Kong
and
DAVID W. CHEUNG
University of Hong Kong
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.
Categories and Subject Descriptors: H.2 [Database Management]: General; H.3.3 [Informa-
tion Search and Retrieval]: General
General Terms: Algorithms, Experimentation, Performance
Additional Key Words and Phrases: Top-k queries, rank aggregation
This work was supported by grant HKU 7160/05E from Hong Kong RGC. Nikos Mamoulis, Kit
Hung Cheng, and David W. Cheung are with the Department of Computer Science, University of
Hong Kong, Pokfulam Road, Hong Kong.