맵리듀스를 이용한 그리드 기반 k-NN 조인 질의처리 알고리즘 (Grid-based k-Nearest Neighbor Join Query Processing Algorithm using MapReduce)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 30권 / 2호 / 103 ~ 115페이지
· 저자명 : 윤들녁, 장미영, 장재우

초록

최근 대용량 데이터를 분석하기 위한 맵리듀스 기반 질의처리 알고리즘이 다양하게 연구되고 있다. 특히, k-NN조인 질의처리 알고리즘은 서로 다른 두 개의 데이터베이스 R과 S가 존재할 때, R의 모든 데이터에 대해 가장거리가 가까운 상위 k개의 S데이터를 탐색하는 알고리즘으로써, 데이터 마이닝 및 분석을 기반으로 하는 응용 분야에서 매우 중요하게 활용되고 있다. 그러나, 대표 연구인 보로노이 기반 k-NN 조인 질의처리 알고리즘은 보로노이 인덱스 구축 비용이 매우 크기 때문에, 업데이트가 빈번하게 발생하는 대용량 데이터에 적합하지 못하다. 아울러 보로노이 셀 정보를 저장하기 위해 사용하는 R-트리는 맵리듀스 환경에서의 분산 병렬 처리에 적합하지 않다.
따라서, 본 논문에서는 새로운 그리드 인덱스 기반의 k-NN 조인 질의 처리 알고리즘을 제안한다. 첫째, 높은 인덱스 구축 비용 문제를 해결하기 위해, 데이터 분포를 고려한 동적 그리드 인덱스 생성 기법을 제안한다. 둘째, 맵리듀스 환경에서 효율적으로 k-NN 조인 질의를 수행하기 위해, 인접셀 정보를 시그니처로 활용하는 후보영역 탐색및 필터링 알고리즘을 제안한다. 이를 통해, R의 각 데이터가 위치한 그리드 셀의 인접 셀만을 탐색하여 관련 데이터만을 맵리듀스의 입력으로 전송하기 때문에 데이터 입출력 및 연산 시간이 크게 감소하는 장점을 지닌다. 마지막으로 성능 평가를 통해 제안하는 기법이 높은 질의 결과 정확도를 보이는 동시에 질의 처리 시간 측면에서 기존기법에 비해 최대 3배의 높은 질의 처리 성능을 나타낸다.

영어초록

Recently, MapReduce based query processing algorithms have been widely studied to analyze bigdata. K-nearest neighbor(k-NN) join algorithm, which aims to produce the k nearest neighbors ofeach point of a data set S from another data set R, has been considered most important in dataanalysis-based applications. However, the existing k-NN join query processing algorithm suffersfrom high index construction cost which makes them unsuitable for big data processing.
Furthermore, to store data partitioning information, the existing algorithm utilizes R-tree which isnot useful in the distributed computing environment. To solve these problems, we propose a newgrid-based k-NN join query processing algorithm. First, to reduce the index construction cost, wedesign a dynamic grid index construction algorithm by considering data distribution. Second, toefficiently perform a k-NN join query in MapReduce, we devise a candidate cell retrieval andpruning method based on data signature. Therefore, our algorithm only retrieves neighboring datafrom the query cell and sends them as an input of MapReduce job. This can greatly reduce thedata transmission and computation overhead. In performance analysis, we prove that our algorithmoutperforms the existing work up to 3 times in terms of query processing time while our algorithmachieves high query result accuracy.

참고자료

· 없음