Processing Top-k Dominating Queries in Metric Spaces

• Published in: ACM transactions on database systems 2016-02, Vol.40 (4), p.1-38
• Main Authors: Tiakas, Eleftherios, Valkanas, George, Papadopoulos, Apostolos N., Manolopoulos, Yannis, Gunopulos, Dimitrios
• Format: Article
• Language: English
• Subjects: Dominance; Dynamic tests; Mathematical analysis; Metric space; Queries; Query processing; Vectors (mathematics)
• ISSN: 0362-5915; 1557-4644
• DOI: 10.1145/2847524

Top - k dominating queries combine the natural idea of selecting the k best items with a comprehensive “goodness” criterion based on dominance. A point p 1 dominates p 2 if p 1 is as good as p 2 in all attributes and is strictly better in at least one. Existing works address the problem in settings where data objects are multidimensional points. However, there are domains where we only have access to the distance between two objects. In cases like these, attributes reflect distances from a set of input objects and are dynamically generated as the input objects change. Consequently, prior works from the literature cannot be applied, despite the fact that the dominance relation is still meaningful and valid. For this reason, in this work, we present the first study for processing top- k dominating queries over distance-based dynamic attribute vectors, defined over a metric space . We propose four progressive algorithms that utilize the properties of the underlying metric space to efficiently solve the problem and present an extensive, comparative evaluation on both synthetic and real-world datasets.