Ranked selection indexes for linear preference queries

Abstract

Data entities from various data sources could be ordered according to a variety of attributes associated with those entities. These orderings result in a ranking of entities in terms of the values in the attribute domains. In query processing, user preferences are desired to be tied to values of specific rank attributes. A way to incorporate such preference is by utilizing a function f that combines user preferences and rank attribute values and returns numerical value. Top-k queries seek to identify the tuples with the highest numerical value. We consider the top-k selection query on relational database: SELECT * FROM S ORDER BY f(t) LIMIT k.We propose efficient indexes on S to find the top-k tuples, for a given linear monotone preference function f . The efficiency of our approach depends on the number of dimensions: the number of rank attributes used to compute f . We present efficient algorithms for two dimensions. Our results for two dimensions improve upon Tsaparas et. al. Our approach is based on convex layers, which is more appropriate for linear preference function.