An Improvement in K-NN Graph Construction with Locality Sensitive Hashing on MapReduce

학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2015. 2. 김형주.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. 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.제 1 장 서론 1 제 2 장 관련 연구 6 제 3 장 배경지식 10 3.1 LSH(Locality Sensitive Hashing) 10 3.1.1 MinHash 11 3.2 아파치 하둡(Apache Hadoop) 12 3.2.1 맵리듀스(MapReduce) 12 제 4 장 LSH를 이용한 k-NN 그래프 생성 15 4.1 문제 정의 15 4.2 MinHash를 이용한 이웃후보 그룹생성 16 4.3 이웃후보 그룹 재구성 17 4.3.1 일정한 그룹사이즈로 그룹 재구성 18 4.3.2 재 해싱을 통한 그룹 재구성 21 4.4 이웃후보 그룹내의 유사도 검사 및 k-NN 추출 24 제 5 장 성능평가 27 5.1 실험설정 27 5.1.1 데이터 셋 27 5.1.2 비교 알고리즘 28 5.1.3 성능평가 기준 29 5.2 실험 결과 30 5.2.1 시간과 정확도 30 5.2.2 정확도와 상대 유사도 계산비율(Scan Rate) 33 5.2.3 정확도와 해시테이블 개수 35 5.2.4 클러스터 증가에 따른 영향 36 5.2.5 잡 수행시간(job completion time)과 리듀스 셔플 바이트(reduce shuffle bytes) 37 5.2.6 맵 수행시간 41 제 6 장 결론 및 향후 연구 42 참고문헌 43 부록 47 Abstract 53Maste