2007 · 182 citations · 23 references
ComputingComputer ScienceData ScienceData ManagementData MiningDatabasesDimension ReductionDimensionality ReductionNearest Neighbor SearchQuery OptimizationQuery ProcessingRanking ProblemsDominance SearchingMulti-dimensional DatabasesMultidimensional IndexingObjectsRanking FunctionsTop-k Query OptimizationTop-k Query ProcessingTop-k Ranking
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. In this paper, we design specialized algorithms that apply on indexed multi-dimensional data and fully exploit the characteristics of the problem. Experiments on synthetic datasets demonstrate that our algorithms significantly outperform a previous skyline-based approach, while our results on real datasets show the meaningfulness of top-k dominating queries.
23
S. Borzsony, Donald Kossmann, Konrad Stocker · 2002 · 2.2K citations
Optimal aggregation algorithms for middleware
Ronald Fagin, Amnon Lotem, Moni Naor · Journal of Computer and System Sciences · 2003 · 941 citations
Progressive skyline computation in database systems
Dimitris Papadias, Yufei Tao, Greg Fu et al. · ACM Transactions on Database Systems · 2005 · 886 citations
Distance browsing in spatial databases
Gı́sli R. Hjaltason, Hanan Samet · ACM Transactions on Database Systems · 1999 · 877 citations · Full text