Nearest-Neighbor Searching Under Uncertainty II
| Autor: | Wuzhou Zhang, Sariel Har-Peled, Boris Aronov, Pankaj K. Agarwal, Jeff M. Phillips, Ke Yi |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Cover tree Computer science Nearest neighbor search 0102 computer and information sciences 02 engineering and technology Nearest neighbour distribution computer.software_genre 01 natural sciences Mathematics (miscellaneous) Best bin first Nearest neighbor graph 010201 computation theory & mathematics 020204 information systems Ball tree 0202 electrical engineering electronic engineering information engineering Computer Science - Computational Geometry Data mining Fixed-radius near neighbors computer Large margin nearest neighbor Computer Science::Databases |
| DOI: | 10.48550/arxiv.1606.00112 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|