Computing ranked selection indexes for linear preference queries

Abstract

The significant increase in data storage and its consumption in today's world brings the focus on efficient query processing. It is general practice to query several data sources for k data entities based on a ranking of certain attributes associated with these entities. In our work, we consider the top-k selection query of relational databases: SELECT * FROM S ORDER BY f(t) LIMIT k We consider the special case of linear monotone preference functions f that are based only on two rank attributes in S. This is an important special case of the top-k join query, and has received much attention. We study the problem of constructing efficient indexes on S, so as to find the top-k tuples, for any given linear monotone preference function f. There are efficient algorithms in the literature to construct such an index for k=2. We present another efficient algorithm for k=2, and also an efficient algorithm for k=3. As in some previous works, our approach is based on convex layers, which are more appropriate for linear monotone preference functions.