2013/05/13 by Ανδρέας Κοσματόπουλος, Kosmatopoulos, Andreas, Kostas Tsichlas +1
Computer Science · #Advanced Database Systems and Queries #Computational Geometry (cs.CG) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1305.2835
openalex publication_date 2013/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let S be a dataset of n 2-dimensional points. The top-k dominating query aims to report the k points that dominate the most points in S. A point p dominates a point q iff all coordinates of p are smaller than or equal to those of q and at least one of them is strictly smaller. The top-k dominating query combines the dominance concept of maxima queries with the ranking function of top-k queries and can be used as an important tool in multi-criteria decision making systems. In this work, we propose novel algorithms for answering semi-dynamic (insertions only) and fully dynamic (insertions and deletions) top-k dominating queries. To the best of our knowledge, this is the first work towards handling (semi-)dynamic top-k dominating queries that offers algorithms with asymptotic guarantees regarding their time and space cost.