An optimal algorithm for approximate nearest neighbor searching in fixed dimensions
An optimal algorithm for approximate nearest neighbor searching in fixed dimensions
复制标题
DOI：
10.1145/293347.293348
复制
发表时间：
1998-11-01
影响因子：
2.5
通讯作者：
Wu, AY
中科院分区：
文献类型：
--
作者：
Arya, S;Mount, DM;Wu, AY
考虑在实际D维空间R-D中的n个数据点的集合，其中使用任何Minkowski度量测量距离。在最近的邻居搜索中，我们将S到数据结构中进行了预处理，因此可以迅速报告S与Q的最接近点Q Epsilon R-D。考虑到任何正真实的epsilon，数据点p是q的距离（1 + epsilon）的最接近q的距离，如果其距离距离距离距离（1 + epsilon）距离真正最近的邻居的距离（1 + epsilon）。我们表明，可以在O（dn log n）时间和O（DN）空间中的R-D中预处理一组n个点，因此给定查询点Q Epsilon R-D和Epsilon> 0，A（1 + Epsilon ） - 可以在o（c（d，epsilon）log n）时间中计算q的最接近邻居，其中c（d，epsilon）小于或等于d [1 + 6d/epsilon]（d）是仅取决于尺寸和epsilon的因素。通常，我们表明，给定一个大于或等于1（1 + epsilon）的整数k在Q最近的k最近的邻居中的approximation以其他O（kd log n）时间计算。
Consider a set 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 epsilon R-d, is the closest point of S to q can be reported quickly. Given any positive real epsilon, a data point p is a (1 + epsilon)-approximate nearest neighbor of q if its distance from q is within a factor of (1 + epsilon) 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 epsilon R-d, and epsilon > 0, a (1 + epsilon)-approximate nearest neighbor of q can be computed in O(c(d,epsilon) log n) time, where c(d,epsilon) less than or equal to d [1 + 6d/epsilon](d) is a factor depending only on dimension and epsilon. In general, we show that given an integer k greater than or equal to 1 (1 + epsilon)-approximations to the k nearest neighbors of q cart be computed in additional O(kd log n) time.