Full Citation

Title: Efficient All Top-k Computation

Citation Type: Miscellaneous

Publication Year: 2011

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: Given a set of objects P and a set of ranking functions F over P, an interesting problem is to compute the top ranked objects for all functions. Evaluation of multiple top-k queries finds application in systems, where there is a heavy workload of ranking queries (e.g., online search engines and product recommendation systems). The simple solution of evaluating the top-k queries one-by-one does not scale well; instead, the system can make use of the fact that similar queries share common results to accelerate search. This paper is the first, to our knowledge, thorough study of this problem. We propose methods that compute all top-k queries in batch. Our first solution applies the block indexed nested loops paradigm, while our second technique is a view-based threshold algorithm. We propose appropriate optimization techniques for the two approaches and demonstrate experimentally that the second approach is consistently the best. In addition, we demonstrate the utility of our approach in solving other complex queries that depend on the computation of multiple top-k queries. We show that our adapted methods for these complex queries outperform the state-of-the-art by orders of magnitude.

User Submitted?: No

Authors: Cheung, David W.L.; Ge, Shen; U, Leong Hou; Mamoulis, Nikos

Publisher: University of Hong Kong

Data Collections: IPUMS USA

Topics: Methodology and Data Collection, Other

Countries: