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 k 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.
In the formulation of expected nearest neighbor (ENN), one considers the expected distance from each data point to the query point. Since the expected distance of any input point only depends on the query point, efficient data structures are available. Recently, Agarwal @cite_17 gave the first nontrivial methods for answering exact or approximate expected nearest neighbor queries under @math , @math , and the squared Euclidean distance, with provable performance guarantee. Efficient data structures are also provided in @cite_17 when the input data is uncertain and the query data is exact.
@cite_17
2071866949 2031212151 2398147718 2155533773
Given a set of n points in d-dimensional Euclidean space, S ⊂ E, and a query point q ∈ E, we wish to determine the nearest neighbor of q, that is, the point of S whose Euclidean distance to q is minimum. The goal is to preprocess the point set S, such that queries can be answered as efficiently as possible. We assume that the dimension d is a constant independent of n. Although reasonably good solutions to this problem exist when d is small, as d increases the performance of these algorithms degrades rapidly. We present a randomized algorithm for approximate nearest neighbor searching. Given any set of n points S ⊂ E, and a constant ǫ > 0, we produce a data structure, such that given any query point, a point of S will be reported whose distance from the query point is at most a factor of (1 + ǫ) from that of the true nearest neighbor. Our algorithm runs in O(log n) expected time and requires O(n log n) space. The data structure can be built in O(n) expected time. The constant factors depend on d and ǫ. Because of the practical importance of nearest neighbor searching in higher dimensions, we have implemented a practical variant of this algorithm, and show empirically that for many point distributions this variant of the algorithm finds the nearest neighbor in moderately large dimension significantly faster than existing practical approaches. Given a set S of n sites (points), and a distance measure d , the nearestneighborsearching problem is to build a data structure so that given a query point q , the site nearest to q can be found quickly. This paper gives data structures for this problem when the sites and queries are in a metric space. One data structure, D(S) , uses a divide-and-conquer recursion. The other data structure, M(S,Q) , is somewhat like a skiplist. Both are simple and implementable. The data structures are analyzed when the metric space obeys a certain sphere-packing bound, and when the sites and query points are random and have distributions with an exchangeability property. This property implies, for example, that query point q is a random element of ( S q ) . Under these conditions, the preprocessing and space bounds for the algorithms are close to linear in n . They depend also on the sphere-packing bound, and on the logarithm of the distanceratio ( (S) ) of S , the ratio of the distance between the farthest pair of points in S to the distance between the closest pair. The data structure M(S,Q) requires as input data an additional set Q , taken to be representative of the query points. The resource bounds of M(S,Q) have a dependence on the distance ratio of S ( )Q . While M(S,Q) can return wrong answers, its failure probability can be bounded, and is decreasing in a parameter K . Here K≤ |Q| n is chosen when building M(S,Q) . The expected query time for M(S,Q) is O(Klog n)log ( (S Q) ) , and the resource bounds increase linearly in K . The data structure D(S) has expected O( log n) O(1) query time, for fixed distance ratio. The preprocessing algorithm for M(S,Q) can be used to solve the all nearest neighbor problem for S in O(n(log n) 2 (log ϒ(S)) 2 ) expected time. We consider the Approximate Nearest Line Search (NLS) problem. Given a set L of N lines in the high dimensional Euclidean space Rd, the goal is to build a data structure that, given a query point q ∈ Rd, reports a line l ∈ L such that its distance to the query is within (1 + e) factor of the distance of the closest line to the query point q. The problem is a natural generalization of the well-studied Approximate Nearest Neighbor problem for point sets (ANN), and is a natural first step towards understanding how to build efficient nearest-neighbor data structures for objects that are more complex than points. Our main result is a data structure that, for any fixed e > 0, reports the approximate nearest line in time (d + log N + 1 e)O(1) using O(N + d)O(1 e2) space. This is the first high-dimensional data structure for this problem with poly-logarithmic query time and polynomial space. In contrast, the best previous data structure for this problem, due to Magen [16], required quasi-polynomial space. Up to polynomials, the bounds achieved by our data structure match the performance of the best algorithm for the approximate nearest neighbor problem for point sets. In this paper, we study a novel form of continuous nearest neighbor queries in the presence of obstacles, namely continuous obstructed nearest neighbor (CONN) search. It considers the impact of obstacles on the distance between objects, which is ignored by most of spatial queries. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CONN query retrieves the nearest neighbor of each point on q according to the obstructed distance, i.e., the shortest path between them without crossing any obstacle. We formulate CONN search, analyze its unique properties, and develop algorithms for exact CONN query processing, assuming that both P and O are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle the CONN retrieval by performing a single query for the entire query segment, and only process the data points and obstacles relevant to the final result, via a novel concept of control points and an efficient quadratic-based split point computation algorithm. In addition, we extend our solution to handle the continuous obstructed k-nearest neighbor (COkNN) search, which finds the k (≥1)nearest neighbors to every point along q based on obstructed distances. A comprehensive experimental evaluation using both real and synthetic datasets has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms.