Scalable K-Nearest Neighbor Graph Construction Based on Greedy Filtering

Information

Title Scalable K-Nearest Neighbor Graph Construction Based on Greedy Filtering
Authors Youngki Park, Sungchan Park, Sang-goo Lee, Woosung Jung
Year 2013 / 5
Keywords K-nearest neighbor graphs, greedy filtering, similarity join
Acknowledgement BLS, NRF
Publication Type International Conference
Publication Proceedings of the 22nd International Conference on World Wide Web 2013 (WWW 2013), pp. 227-228
Link url doi

Abstract

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 efficient 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.