Nearest-neighbor searching under uncertainty II

Pankaj K. Agarwal; Boris Aronov; Sariel Har-Peled; Jeff M. Phillips; Ke Yi; Wuzhou Zhang

doi:10.1145/2955098

Nearest-neighbor searching under uncertainty II

Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Jeff M. Phillips, Ke Yi, Wuzhou Zhang

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Article number	3
Journal	ACM Transactions on Algorithms
Volume	13
Issue number	1
DOIs	https://doi.org/10.1145/2955098
State	Published - Oct 2016

Keywords

Approximate nearest neighbor
Indexing uncertain data
Probabilistic nearest neighbor
Threshold queries

ASJC Scopus subject areas

Mathematics (miscellaneous)

Access to Document

10.1145/2955098

Cite this

@article{54db591b87e3452285c4827036612c8c,

title = "Nearest-neighbor searching under uncertainty II",

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.",

keywords = "Approximate nearest neighbor, Indexing uncertain data, Probabilistic nearest neighbor, Threshold queries",

author = "Agarwal, {Pankaj K.} and Boris Aronov and Sariel Har-Peled and Phillips, {Jeff M.} and Ke Yi and Wuzhou Zhang",

note = "Publisher Copyright: {\textcopyright} 2016 ACM.",

year = "2016",

month = oct,

doi = "10.1145/2955098",

language = "English (US)",

volume = "13",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - Nearest-neighbor searching under uncertainty II

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Har-Peled, Sariel

AU - Phillips, Jeff M.

AU - Yi, Ke

AU - Zhang, Wuzhou

PY - 2016/10

Y1 - 2016/10

N2 - 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.

AB - 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.

KW - Approximate nearest neighbor

KW - Indexing uncertain data

KW - Probabilistic nearest neighbor

KW - Threshold queries

UR - http://www.scopus.com/inward/record.url?scp=84992168545&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84992168545&partnerID=8YFLogxK

U2 - 10.1145/2955098

DO - 10.1145/2955098

M3 - Article

AN - SCOPUS:84992168545

SN - 1549-6325

VL - 13

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 3

ER -

Nearest-neighbor searching under uncertainty II

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this