Superseding nearest neighbor search on uncertain spatial databases

This paper proposes a new problem, called superseding nearest neighbor search, on uncertain spatial databases, where each object is described by a multidimensional probability density function. Given a query point q, an object is a nearest neighbor (NN) candidate if it has a nonzero probability to be the NN of q. Given two NN-candidates o1 and o2, o1 supersedes o2 if o1 is more likely to be closer to q. An object is a superseding nearest neighbor (SNN) of q, if it supersedes all the other NN-candidates. Sometimes no object is able to supersede every other NN-candidate. In this case, we return the SNN-corethe minimum set of NN-candidates each of which supersedes all the NN-candidates outside the SNN-core. Intuitively, the SNN-core contains the best objects, because any object outside the SNN-core is worse than all the objects in the SNN-core. We show that the SNN-core can be efficiently computed by utilizing a conventional multidimensional index, as confirmed by extensive experiments. © 2010 IEEE.

Duke Scholars

Author Jian Pei Computer Science