Reverse ranking query over imprecise spatial data
Ken C. K. Lee, Mao Ye, Wang-Chien Lee · 2010
The reverse rank of a (data) object o with respect to a given query object q (that measures the relative nearness of q to o) is said to be k when q is the k-th nearest neighbor of o in a geographical space. Based on the notion of reverse ranks, a Reverse Ranking (RR) query determines t objects with the smallest k's with respect to a given query object q. In many situations that locations of objects and a query object can be imprecise, objects would receive multiple possible k's. In this paper, we propose a notion of expected reverse ranks and evaluation of RR queries over imprecise data based on expected reverse ranks. For any object o, an expected reverse rank kk is a weighted average of possible reverse ranks for individual instances of o with respect to different instances of a given query object q by taking their probabilities into account. We devise and present incremental kk computation and two kk-Estimating algorithms to efficiently evaluate RR queries over imprecise data. The efficiency of our approach is demonstrated through experiments.