TY - JOUR
T1 - Nearest-Neighbor Searching Under Uncertainty I
AU - Agarwal, Pankaj K.
AU - Efrat, Alon
AU - Sankararaman, Swaminathan
AU - Zhang, Wuzhou
N1 - Funding Information:
The work of P. Agarwal and W. Zhang was supported by NSF under Grants CCF-09-40671, CCF-10-12254, and CCF-11-61359, by ARO Grants W911NF-07-1-0376 and W911NF-08-1-0452, and by an ERDC contract W9132V-11-C-0003. The work of A. Efrat and S. Sankararaman was supported by NSF CAREER Grant 0348000.
Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.
PY - 2017/10/1
Y1 - 2017/10/1
N2 - Nearest-neighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, 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 and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an ε-approximate ENN , for a given error parameter 0 < ε< 1 , under different distance functions. These methods build a data structure of near-linear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or ε-approximate ENN queries with provable performance guarantees. Moreover, we extend our results to answer exact or ε-approximate k-ENN queries.
AB - Nearest-neighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, 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 and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an ε-approximate ENN , for a given error parameter 0 < ε< 1 , under different distance functions. These methods build a data structure of near-linear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or ε-approximate ENN queries with provable performance guarantees. Moreover, we extend our results to answer exact or ε-approximate k-ENN queries.
KW - Approximate nearest neighbor (ANN)
KW - Nearest-neighbor queries
KW - Queries on uncertain data
UR - http://www.scopus.com/inward/record.url?scp=85021825579&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85021825579&partnerID=8YFLogxK
U2 - 10.1007/s00454-017-9903-x
DO - 10.1007/s00454-017-9903-x
M3 - Article
AN - SCOPUS:85021825579
SN - 0179-5376
VL - 58
SP - 705
EP - 745
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 3
ER -