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