Superseding Nearest Neighbor Search on Uncertain Spatial Databases
Lists
Only you see this
Abstract
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 o <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> and o <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> , o <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> supersedes o <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> if o <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> 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-core-the 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.
BibTeX
@article{yuen2010superseding,
author = {Sze Man Yuen and Yufei Tao and Xiaokui Xiao and Jian Pei and Donghui Zhang},
title = {{Superseding Nearest Neighbor Search on Uncertain Spatial Databases}},
journal = {IEEE Trans. Knowl. Data Eng.},
year = {2010},
url = {https://openreview.net/forum?id=jPbqe_F47ac},
}Loading related content...