정보과학회논문지 (Journal of KIISE)
Current Result Document :
| 한글제목(Korean Title) |
맵리듀스를 이용한 그리드 기반 인덱스 생성 및 k-NN 조인 질의 처리 알고리즘 |
| 영문제목(English Title) |
Grid-based Index Generation and k-nearest-neighbor Join Query-processing Algorithm using MapReduce |
| 저자(Author) |
장미영
장재우
Miyoung Jang
Jae Woo Chang
|
| 원문수록처(Citation) |
VOL 42 NO. 11 PP. 1303 ~ 1313 (2015. 11) |
한글내용
(Korean Abstract) |
맵리듀스는 대용량 데이터 처리를 위한 시스템 안정성과 유용성을 제공한다. 맵리듀스 기반 k-최근접점 조인 질의처리 알고리즘은 두 데이터 집합 R과 S를 기반으로 R의 모든 레코드에 대해 S의 데이터 중 가장 인접한 k개의 레코드를 탐색하는 알고리즘으로써, 대용량 데이터 분석을 위한 중요한 질의 처리 알고리즘이다. 그러나 기존 k-최근접점 조인 질의처리 알고리즘은 높은 인덱스 구축비용 문제로 인해 대용량 데이터 처리에 적합하지 않은 문제점을 지닌다. 따라서, 본 논문에서는 그리드 기반 인덱스 생성 및 k-최근접점 질의 처리 알고리즘을 제안한다. 제안하는 기법은 질의 셀로부터 인접한 데이터만을 찾아 맵리듀스 테스크에 전송함으로써 데이터 전송 및 k-최근접점 연산 오버헤드를 줄인다. 성능평가를 통해, 제안하는 기법이 정확 매칭 질의를 제공하는 동시에 기존 기법에 비해 질의 처리 시간 측면에서 최대 7배의 성능을 개선함을 보인다.
|
영문내용
(English Abstract) |
MapReduce provides high levels of system scalability and fault tolerance for large-size data processing. A MapReduce-based k-nearest-neighbor(k-NN) join algorithm seeks to produce the k nearest-neighbors of each point of a dataset from another dataset. The algorithm has been considered important in bigdata analysis. However, the existing k-NN join query-processing algorithm suffers from a high index-construction cost that makes it unsuitable for the processing of bigdata. To solve the corresponding problems, we propose a new grid-based, k-NN join query-processing algorithm. Our algorithm retrieves only the neighboring data from a query cell and sends them to each MapReduce task, making it possible to improve the overhead data transmission and computation. Our performance analysis shows that our algorithm outperforms the existing scheme by up to seven-fold in terms of the query-processing time, while also achieving high extent of query-result accuracy.
|
| 키워드(Keyword) |
데이터 분산 처리 알고리즘
맵리듀스
k-최근접점 조인 질의처리 알고리즘
그리드 인덱스
|
| 파일첨부 |
PDF 다운로드
|
