Top-k query processing with multidimensional range search

An m-dimensional top-k query (with m search conditions) is primarily processed by scanning the corresponding m index lists in descending score orders in an interleaved manner (and by making judicious random accesses to look up index entries of specific data items). In this paper a new algorithm is proposed that makes use of a data structure that facilitates multidimensional range search. An m-dimensional top-k query can be processed by searching for the data items that satisfies a range of score over each dimension. At every step of the algorithm a new set of ranges (one for each dimension) is specified such that more accurate tuples are added in the candidate top-k set. The process continues till we get the actual top-k data items. The incremented range set is specified with the help of the statistics of the distribution of data items in m-dimensional space. Thus, efficiency of the algorithm very much depends on the proper study and analysis of the distribution of the data items in the m-dimensional space and the data structure used.