MapReduce 환경에서 LSH 기반의 K-NN 그래프 생성 알고리즘의 개선

Abstract

k-Nearest Neighbor(k-NN)그래프는 모든 노드에 대한 k-NN 정보를 나타내는 데이터 구조로써, 많은 정보검색 및 추천 시스템에서 k-NN그래프를 활용하고 있다. 이러한 장점에도 불구하고 brute-force방법의 k-NN그래프 생성 방법은 O(n^2)의 시간복잡도를 갖기 때문에 빅데이터 셋에 대해서는 처리가 곤란하다. 따라서, 고차원, 희소 데이터에 효율적인 Locality Sensitive Hashing 기법을 분산환경인 MapReduce 환경에서 사용하여 k-NN그래프를 생성하는 알고리즘이 연구되고 있다. K-NN 그래프 생성은 사용자를 이웃후보 그룹으로 만들고 후보그룹 내의 쌍에 대해서만 brute-force하게 유사도를 계산하는 divide-and-conquer(two-stage) 방법을 사용했다. 특히, 그래프 생성과정 중 유사도 계산하는 부분이 가장 많은 시간이 소요되므로 후보 그룹을 어떻게 만드는 것인지가 중요하다. 기존의 방법은 사이즈가 큰 후보그룹을 방지하는데 한계점이 있다. 본 논문에서는 효율적인 k-NN 그래프 생성을 위하여 사이즈가 큰 후보그룹을 hierarchical LSH를 사용하여 재구성하는 알고리즘을 제시하였다. 실험 결과 본 논문에서 제시한 방법은 기존의 방법보다 빠르게 더 정확한 근사 그래프를 생성함을 확인하였다.

The k nearest neighbor (k-NN) graph construction is an important operation with many web related applications, including collaborative filtering, similarity search, and many others in data mining and machine learning. Despite its many elegant properties, the brute-force k-NN graph construction method has computational complexity of O(n^2), which is prohibitive for large scale data sets. <Key, Value> based distributed frameworks, MapReduce is gaining increasingly widespread use in applications that process large amounts of data. Based on the divide-and-conquer(two-stage) strategy, we engage the locality sensitive hashing technique which is used for high-dimension and sparse data to divide users into small groups, and calculate similarity using brute-force method on MapReduce. Specifically, generating candidate group stage is important since brute-force calculation is performed in following step. In this paper, we proposed an efficient algorithm for approximating k-NN graphs by re-grouping candidate group using hierarchical LSH. Experimental results show that our approach is more effective than existing method in aspects of graph accuracy and scan rate.