Exact and Approximate Generic Multi-criteria Top-k Query Processing

Many algorithms for multi-criteria top-k query processing with ranking predicates have been proposed, but little effort has been directed toward genericity, i.e. supporting any type of access to the lists of predicate scores (sorted and/or random), or any access cost settings. In this paper we propose a general approach to exact and approximate generic top-k processing. To this end, we propose a general framework (GF) for generic top-k processing, able to express any top-k algorithm and present within this framework a first comparison between generic algorithms. In previous work, we proposed BreadthRefine (BR), a generic algorithm that considers the current top-k candidates as a whole instead of focusing on the best candidate for score refinement, then we compared it with specific top-k algorithms. In this paper, we propose two variants of existing generic strategies and experimentally compare them with the BR breadth-first strategy, showing that BR leads to better execution costs. We also extend the notion of theta-approximation to the GF framework and present a first experimental study of the approximation potential of top-k algorithms on early stopping.