Abstract | ||
---|---|---|
Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has a wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest-neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability and (ii) estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1145/2955098 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Queries on uncertain data,Nearest-neighbor queries,Approximate nearest neighbor,\((\mathop {\mathrm {ANN}})\),68P05,68P10,68P20 | R-tree,Data mining,Fixed-radius near neighbors,Best bin first,Ball tree,Nearest neighbor graph,Nearest neighbour distribution,Cover tree,Mathematics,Nearest neighbor search | Journal |
Volume | Issue | ISSN |
13 | 1 | 1549-6325 |
Citations | PageRank | References |
1 | 0.35 | 20 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pankaj K. Agarwal | 1 | 5257 | 593.81 |
Boris Aronov | 2 | 1430 | 149.20 |
Sariel Har-Peled | 3 | 2630 | 191.68 |
Jeff M. Phillips | 4 | 536 | 49.83 |
Ke Yi | 5 | 1659 | 77.79 |
Wuzhou Zhang | 6 | 37 | 3.99 |