TY - GEN
T1 - Nearest-neighbor searching under uncertainty
AU - Agarwal, Pankaj K.
AU - Efrat, Alon
AU - Sankararaman, Swaminathan
AU - Zhang, Wuzhou
PY - 2012
Y1 - 2012
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 dierent distance functions. These methods build an index 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.
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 dierent distance functions. These methods build an index 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.
KW - approximate nearest neighbor
KW - expected nearest neighbor (enn)
KW - indexing uncertain data
KW - nearest-neighbor queries
UR - http://www.scopus.com/inward/record.url?scp=84862649949&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862649949&partnerID=8YFLogxK
U2 - 10.1145/2213556.2213588
DO - 10.1145/2213556.2213588
M3 - Conference contribution
AN - SCOPUS:84862649949
SN - 9781450312486
T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
SP - 225
EP - 236
BT - PODS '12 - Proceedings of the 31st Symposium on Principles of Database Systems
T2 - 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '12
Y2 - 21 May 2012 through 23 May 2012
ER -