Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
复制标题
DOI：
10.4086/toc.2012.v008a014
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
Sariel Har-Peled;P. Indyk;R. Motwani
中科院分区：
文献类型：
--
作者：
Sariel Har-Peled;P. Indyk;R. Motwani
本文提出了两种求解高维空间中近似最近邻问题的算法。对于存在于IR d中的大小为n的数据集，算法需要仅在n和d中多项式的空间，同时实现在n中次线性且在d中多项式的查询时间。我们还展示了其他高维几何问题，如近似最小生成树的应用。
We present two algorithms for the approximate nearest neighbor problem in high dimensional spaces. For data sets of size n living in IR d , the algorithms require space that is only polynomial in n and d , while achieving query times that are sub-linear in n and polynomial in d . We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree.