Efficient and generic evaluation of ranked queries
Wen Jin, Jignesh M. Patel · 2011
An important feature of the existing methods for ranked top-k processing is to avoid searching all the objects in the underlying dataset, and limiting the number of random accesses to the data. However, the performance of these methods degrades rapidly as the number of random accesses increases. In this paper, we propose a novel and general sequential access scheme for top-k query evaluation, which outperforms existing methods. We extend this scheme to efficiently answer top-k queries in subspace and on dynamic data. We also study the "dual" form of top-k queries called "ranking" queries, which returns the rank of a specified record/object, and propose an exact as well as two approximate solutions. An extensive empirical evaluation validates the robustness and efficiency of our techniques.