Nearest-Neighbor Searching Under Uncertainty II

被引：14

作者：

Agarwal, Pankaj K. ^{[1
]}

Aronov, Boris ^{[2
]}

Har-Peled, Sariel ^{[3
]}

Phillips, Jeff M. ^{[4
]}

Yi, Ke ^{[5
]}

Zhang, Wuzhou ^{[6
]}

机构：

[1] Duke Univ, Dept Comp Sci, Box 90129, Durham, NC 27708 USA

[2] NYU, Tandon Sch Engn, Dept Comp Sci & Engn, Brooklyn, NY 11201 USA

[3] Univ Illinois, Dept Comp Sci, 201 N Goodwin Ave, Urbana, IL 61801 USA

[4] Univ Utah, Sch Comp, 50 S Cent Campus Dr, Salt Lake City, UT 84108 USA

[5] Hong Kong Univ Sci & Technol, Dept Comp Sci & Engn, Hong Kong, Hong Kong, Peoples R China

[6] Apple Inc, 1 Infinite Loop, Cupertino, CA 95014 USA

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2016年 / 13卷 / 01期

基金：

美国国家科学基金会;

关键词：

Indexing uncertain data; probabilistic nearest neighbor; approximate nearest neighbor; threshold queries; QUERIES;

D O I：

10.1145/2955098

中图分类号：

TP301 [理论、方法];

学科分类号：

080201 [机械制造及其自动化];

摘要：

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.

引用

页数：25

共 29 条

[1]

Afshani P, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P180

[2]

Agarwal P., 2012, Proceedings of the 31st ACM Symposium on Principles of Database Systems (PODS), P225, DOI DOI 10.1145/2213556.2213588

[3]

Agarwal P. K., 2016, HDB DISCRETE COMPUTA

[4]

Agarwal PK, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P49, DOI 10.1016/B978-044482537-7/50003-6

[5]

Constructing levels in arrangements and higher order Voronoi diagrams [J].

Agarwal, PK ;

de Berg, M ;

Matousek, J ;

Schwarzkopf, O .

SIAM JOURNAL ON COMPUTING, 1998, 27 (03) :654-667

[6]

Aggarwal CC, 2009, ADV DATABASE SYST, V35, P1, DOI 10.1007/978-0-387-09690-2

[7]

[Anonymous], 1995, Davenport-Schinzel Sequences and Their Geometric Applications

[8]

[Anonymous], 2011, MATH SURVEYS MONOGRA

[9]

GENERALIZED DIRICHLET TESSELLATIONS [J].

ASH, PF ;

BOLKER, ED .

GEOMETRIAE DEDICATA, 1986, 20 (02) :209-243

[10]

Bernecker T, 2011, PROC INT CONF DATA, P339, DOI 10.1109/ICDE.2011.5767908

← 1 2 3 →