Metric-Based Top-k Dominating Queries
Eleftherios Tiakas, George Valkanas, Apostolos N. Papadopoulos, Yannis Manolopoulos · 2014
Top-k dominating queries combine the natural idea of se-lecting the k best items with a comprehensive \\goodness" criterion based on dominance. A point p1 dominates p2 if p1 is as good as p2 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 dis-tance between two objects. In cases like these, attributes re ect distances from a set of input objects and are dynam-ically generated as the input objects change. Consequently, prior works from the literature can not be applied, despite the fact that the dominance relation is still meaningful and valid. For this reason, in this work, we present the rst study for processing top-k dominating queries over distance-based dynamic asttribute vectors, dened over a metric space. We propose four progressive algorithms that utilize the proper-ties of the underlying metric space to eciently solve the problem, and present an extensive, comparative evaluation on both synthetic and real world data sets.