Multi-dimensional top-k dominating queries |
| |
Authors: | Man Lung Yiu Nikos Mamoulis |
| |
Affiliation: | (1) Department of Computer Science, Aalborg University, Aalborg, Denmark;(2) Department of Computer Science, University of Hong Kong, Hong Kong, China |
| |
Abstract: | The top-k dominating query returns k data objects which dominate the highest number of objects in a dataset. This query is an important tool for decision support
since it provides data analysts an intuitive way for finding significant objects. In addition, it combines the advantages
of top-k and skyline queries without sharing their disadvantages: (i) the output size can be controlled, (ii) no ranking functions
need to be specified by users, and (iii) the result is independent of the scales at different dimensions. Despite their importance,
top-k dominating queries have not received adequate attention from the research community. This paper is an extensive study on
the evaluation of top-k dominating queries. First, we propose a set of algorithms that apply on indexed multi-dimensional data. Second, we investigate
query evaluation on data that are not indexed. Finally, we study a relaxed variant of the query which considers dominance
in dimensional subspaces. Experiments using synthetic and real datasets demonstrate that our algorithms significantly outperform
a previous skyline-based approach. We also illustrate the applicability of this multi-dimensional analysis query by studying
the meaningfulness of its results on real data. |
| |
Keywords: | Top-k retrieval Preference dominance Score counting |
本文献已被 SpringerLink 等数据库收录! |
|