Reverse ranking query over imprecise spatial data

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 κ when q is the κ-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 κ'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 κ'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 κ̄ 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 κ̄ computation and two κ̄-Estimating algorithms to efficiently evaluate RR queries over imprecise data. The efficiency of our approach is demonstrated through experiments.