.png){kind=icon}
返回
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
.png){kind=icon}
OA
AI
DOI：10.1145/293347.293348.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Consider a set of
S
of
n
data points in real
d
-dimensional space, R
d
, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess
S
into a data structure, so that given any query point
q
∈ R
d
, is the closest point of S to
q
can be reported quickly. Given any positive real ϵ, data point
p
is a (1 +ϵ)-
approximate nearest neighbor
of
q
if its distance from
q
is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of
n
points in R
d
in
O(dn
log
n
) time and
O(dn)
space, so that given a query point
q
∈ R
d
, and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of
q
can be computed in
O
(
c
d
, ϵ
log
n
) time, where
c
d,ϵ
≤
d
⌈1 + 6d/ϵ⌉
d
is a factor depending only on dimension and ϵ. In general, we show that given an integer
k
≥ 1, (1 + ϵ)-approximations to the
k
nearest neighbors of
q
can be computed in additional
O(kd
log
n
) time.
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息