The L1 Nearest Neighbor Searching with Uncertain Queries
Haitao Wang, Wuzhou Zhang · arXiv (Cornell University) · 2012
In this paper, we present algorithms and data structures for the top-k nearest neighbor searching where the input points are exact and the query point is uncertain under the L1 distance metric in the plane. The uncertain query point is represented by a discrete probability density function, and the goal is to return the top-k expected nearest neighbors, which have the smallest expected distances to the query point. Given a set of n exact points in the plane, we build an O(n log n log log n)-size data structure in O(n log n log log n) time, such that for any uncertain query point with m possible locations and any integer k with 1\leq k\leq n, the top-k expected nearest neighbors can be found in O(mlogm + (k+m)log^2 n) time. Even for the special case where k = 1, our result is better than the previously best method (in PODS 2012), which requires O(n log^2 n) preprocessing time, O(n log^2 n) space, and O(m^2 log^3 n) query time. In addition, for the one-dimensional version of this problem, our approach can build an O(n)-size data structure in O(n log n) time that can support O(min{mk,mlog m} + k + log n) time queries and the query time can be reduced to O(k+m+log n) time if the locations of Q are given sorted. In fact, the problem is equivalent to the aggregate or group nearest neighbor searching with the weighted SUM as the aggregate distance function operator.