Non-zero probability of nearest neighbor searching

Nearest neighbor (NN) searching is a challenging problem in data management, and has been widely studied in data mining, pattern recognition, and computational geometry. The goal of NN searching is an efficient report of the data nearest to a given object as a query. In most studies, both the data and the query are assumed to be precise. However, due to the real applications of NN searching such as the tracking and locating services, GIS, and data mining, it is possible for both the data and the query to be imprecise. In such situations, a natural way to handle the issue is to report the data that has a non-zero probability (called the non-zero NN) as the NN of a given query. Formally, let P be a set of n uncertain points modeled by some regions. We first consider the following variation in an NN searching problem under uncertainty. If the data is certain and the query is an uncertain point modeled by an axis-aligned parallel segment, we propose an efficient algorithm in O(n logn) pre-processing and O(logn ? k ) query time, where k is the number of non-zero NNs. If both the query and the data are uncertain points modeled by distinct unit segments parallel to the x-axis, we propose an efficient algorithm that reports the non-zero NNs under Manhattan metric in 2 2 O(n ? (n )) pre-processing and O(logn ? k ) query time, where ? (.) is the extremely slow growing functional inverse of the Ackermann function. Finally, for the arbitrarily length segments parallel to the xaxis, we propose an approximation algorithm that reports a non-zero NN with a maximum error L in 2 2 O(n ? (n )) pre-processing and O(logn ? k ) query time, where L is the query length.