Scalable k-nearest neighbor graph construction based on greedy filtering
Scalable k-nearest neighbor graph construction based on greedy filtering
复制标题
DOI：
10.1145/2487788.2487905
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
Youngki Park;Sungchan Park;Sang-goo Lee;Woosung Jung
中科院分区：
文献类型：
--
作者：
Youngki Park;Sungchan Park;Sang-goo Lee;Woosung Jung
K-最近邻图（K-NNG）构建是信息检索和推荐系统领域的原始操作。然而，随着节点数量或维度的增加，现有的 K-NNG 构建方法表现不佳。在本文中，我们提出了贪婪过滤，这是一种有效且可扩展的算法，用于通过仅匹配大值的维度来选择最近邻居的候选者。实验结果表明，我们基于贪婪过滤的 K-NNG 构建方案在保证高召回率的同时，对于大型高维数据的速度比最先进的算法快 5 到 6 倍。
K-Nearest Neighbor Graph (K-NNG) construction is a primitive operation in the field of Information Retrieval and Recommender Systems. However, existing approaches to K-NNG construction do not perform well as the number of nodes or dimensions scales up. In this paper, we present greedy filtering, an effcient and scalable algorithm for selecting the candidates for nearest neighbors by matching only the dimensions of large values. The experimental results show that our K-NNG construction scheme, based on greedy filtering, guarantees a high recall while also being 5 to 6 times faster than state-of-the-art algorithms for large, high-dimensional data.