Efficient processing of top-k dominating queries on multi-dimensional data

Man Lung Yiu, Nikos Mamoulis

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

154 Citations (Scopus)


2007 VLDB Endowment, ACM. 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.
Original languageEnglish
Title of host publication33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings
PublisherAssociation for Computing Machinery, Inc
Number of pages12
ISBN (Electronic)9781595936493
Publication statusPublished - 1 Jan 2007
Externally publishedYes
Event33rd International Conference on Very Large Data Bases, VLDB 2007 - University of Vienna, Vienna, Austria
Duration: 23 Sep 200727 Sep 2007


Conference33rd International Conference on Very Large Data Bases, VLDB 2007

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems and Management
  • Information Systems
  • Software

Cite this