[논문]맵리듀스를 이용한 효율적인 k-NN 조인 질의처리 알고리즘

윤들녁; 장미영; 장재우

맵리듀스를 이용한 효율적인 k-NN 조인 질의처리 알고리즘
Efficient k-Nearest Neighbor Join Query Processing Algorithm using MapReduce 원문보기

윤들녁 (전북대학교 컴퓨터공학과) , 장미영 (전북대학교 컴퓨터공학과) , 장재우 (전북대학교 IT정보공학과)

대용량 데이터를 분석하기 위한 맵리듀스 기반 k-NN 조인 질의처리 알고리즘은 최근 데이터 마이닝 및 분석을 기반으로 하는 응용 분야에서 매우 중요하게 활용되고 있다. 그러나, 대표적인 연구인 보로노이 기반 k-NN 조인 질의처리 알고리즘은 보로노이 인덱스 구축 비용이 매우 크기 때문에 대용량 데이터에 적합하지 못하다. 아울러 보로노이 셀 정보를 저장하기 위해 사용하는 R-트리는 맵리듀스 환경의 분산 병렬 처리에 적합하지 않다. 따라서 본 논문에서는 새로운 그리드 인덱스 기반의 k-NN 조인 질의 처리 알고리즘을 제안한다. 첫째, 높은 인덱스 구축 비용 문제를 해결하기 위해, 데이터 분포를 고려한 동적 그리드 인덱스 생성 기법을 제안한다. 둘째, 맵리듀스 환경에서 효율적으로 k-NN 조인 질의를 수행하기 위해, 인접셀 정보를 시그니처로 활용하는 후보영역 탐색 및 필터링 알고리즘을 제안한다. 마지막으로 성능 평가를 통해 제안하는 기법이 질의 처리 시간 측면에서 기존 기법에 비해 최대 3배 높은 질의 처리 성능을 나타냄을 보인다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 대용량 데이터 처리에 효율적인 k-NN 조인 질의 처리 알고리즘을 제안한다. 첫째, 높은 인덱스 구축 비용 문제를 해결하기 위해, 데이터 분포를 고려한 동적 인덱스를 제안한다.
본 논문에서는 맵리듀스 환경에서 효율적으로 k-NN 조인 질의를 수행하기 위한 그리드 인덱스 기반 k-NN 조인 질의처리 알고리즘을 제안한다. 제안하는 기법은 기존 k-NN 조인 질의처리 연구인 PBJ15]와 성능비교를 통해 질의 처리 시간 측면에서 평균 17배 우수한 성능을 제시함을 입증하였다.

제안 방법

Wei Lu et al.⑸이 제안한 맵리듀스를 이용한보로노이 기반 k-NN 조인 질의처리 알고리즘은 총 3단계를 통해 수행된다. 첫째, 전처리 단계에서 k-NN 조인에 대한 연산 비용을 줄이기 위해 日과 S에 대한 pivot을 랜덤으로 선정한다.
첫째, 전처리 단계에서 k-NN 조인에 대한 연산 비용을 줄이기 위해 日과 S에 대한 pivot을 랜덤으로 선정한다. 둘째, 1단계 맵리듀스 단계에서는 선정한 pivot을 이용하여 각 데이터 셋 S와 R에 대한보로노이 인덱스를 구축한다. 아울러, 각 보로노이 파티션에 할당된 데이터 셋 개수, 파티션간의 최대/최소거리, 가장 가까운 k개의 거리에 대한 파티션 통계정보(Partition statics) 정보를수집한다.
첫째, 높은 인덱스 구축 비용 문제를 해결하기 위해, 데이터 분포를 고려한 동적 인덱스를 제안한다. 둘째, 맵리듀스 환경에서 효율적으로 k-NN 조인 질의를 수행하기 위해, 인접 셀 정보를 시그니처로 활용하는 후보영역 탐색 및 필터링 알고리즘을 제안한다. 이를 통해, 데이터 입 출력 및 연산 시 간이 크게 감소하는 장점을 지닌다.
이때, 모든 맵 함수에서 병렬적으로 비트 정보를 생성하기 때문에, 리듀스 함수에서 이를 집계하여 최종 그리드 셀에 대한비트열을 생성한다. 또한 셔플 (suffle) 단계를 통해 동일한 그리드 셀 아이디를 지니는 데이터를 그룹화 함으로써, 같은 리듀스 함수에서 처리할 수 있도록 한다. 리듀스 함수는 생성된 비트열 정보 및 그리드 셀의 밀도를 계산함으로써, 적절한 그리드 분할 값을 계산한다.
본 장에서는 제안하는 그리드 인덱스 기반 k-NN 조인 질의 처리 알고리즘의 우수성을 검증하기 위해, 기존 PBJ[5] 기법과 제안하는 기법의 질의 처리 성능을 비교한다. 성능평가의 실험 환경은<표 1>과 같다.
둘째, 1단계 맵리듀스 단계에서는 선정한 pivot을 이용하여 각 데이터 셋 S와 R에 대한보로노이 인덱스를 구축한다. 아울러, 각 보로노이 파티션에 할당된 데이터 셋 개수, 파티션간의 최대/최소거리, 가장 가까운 k개의 거리에 대한 파티션 통계정보(Partition statics) 정보를수집한다. 마지막으로, 2단계 리듀스 함수에서는 데이터 셋 日의 파티션 에 대해 k-NN 후보를 포함하는 § 서브셋을 탐색하여 최종 k-NN 후보를 탐색하여 결과를 반환한다.
질의 점 (r_q)과 탐색된 S 데이터 간의 거리를 측정하여 동일한 셀에 저장된 데이터 중에서 k-NN 데이터를 찾고, 거리를 계산한다. 아울러, 본 논문에서는 k-NN의 정확도를 보장하기 위해 외부 인접셀까지의 확장을 수행한다. 이때, 불필요한 확장으로 인한 k-NN 연산 오버헤드를 감소하기 위해, 질의 셀로부터 총 8방향
만약 최근접 변까지의 거리가 k-NN 데이터까지의 거리보다 작다면, 해당 변의 방향으로 확장을 수행한다. 아울러, 해당 변을 이루는 꼭지점 중 질의와 가장 근접한 꼭지점의 방향을 고려하여 추가 확장 여부를 계산하고, 조건을 만족할 경우 추가 확장을 수행한다. 질의 셀의 외부 확장은 조건을 만족하는 셀이 없을 때까지 반복한다.
제안하는 시스템 구조는 전처리 단계, 1단계, 2단계 맵리듀스로 구성된다, (그림 2).
이용하여 탐색한다. 질의 점 (r_q)과 탐색된 S 데이터 간의 거리를 측정하여 동일한 셀에 저장된 데이터 중에서 k-NN 데이터를 찾고, 거리를 계산한다. 아울러, 본 논문에서는 k-NN의 정확도를 보장하기 위해 외부 인접셀까지의 확장을 수행한다.
k-NN 조인 질의 처리 알고리즘을 제안한다. 첫째, 높은 인덱스 구축 비용 문제를 해결하기 위해, 데이터 분포를 고려한 동적 인덱스를 제안한다. 둘째, 맵리듀스 환경에서 효율적으로 k-NN 조인 질의를 수행하기 위해, 인접 셀 정보를 시그니처로 활용하는 후보영역 탐색 및 필터링 알고리즘을 제안한다.
⑸이 제안한 맵리듀스를 이용한보로노이 기반 k-NN 조인 질의처리 알고리즘은 총 3단계를 통해 수행된다. 첫째, 전처리 단계에서 k-NN 조인에 대한 연산 비용을 줄이기 위해 日과 S에 대한 pivot을 랜덤으로 선정한다. 둘째, 1단계 맵리듀스 단계에서는 선정한 pivot을 이용하여 각 데이터 셋 S와 R에 대한보로노이 인덱스를 구축한다.

데이터처리

성능평가의 실험 환경은<표 1>과 같다. MapReduce 환경구축을 위해 범용 pc 7대에서 하둡 2.2.0을 이용하여 기존 연구의 알고리즘 및 제안하는 알고리즘을 구현하고, 성능 평가를 수행하였다.

성능/효과

또한 (그림 9(b))는 그리드 분할 수가 100, k가 100일 때, 데이터 크기의 변화에 따른 질의 처리 시간을 나타낸다. 데이터 크기가 증가될수록 셀에 포함되는 데이터 수가 증가하여 질의 처리 시간이 증가하나, 기존 연구와 비교했을 때 평균 17배 빠른 것을 확인할 수 있다.
따라서 대용량 데이터 및 업데이트가 빈번하게 발생하는 위치데이터 등에 적합하지 않은 특징을 나타낸다. 반면, 제안하는 기법은 그리드를 사용하기 때문에 분할 영역 연산이 빠르고 한번 인덱스를 구축하면 데이터 업데이트가 용이하다는 특성을 가지고 있으므로, PBJ에 비해 대용량 데이터 처리 및 인덱스 구축에 적합하다.
제안하는 기법은 기존 k-NN 조인 질의처리 연구인 PBJ15]와 성능비교를 통해 질의 처리 시간 측면에서 평균 17배 우수한 성능을 제시함을 입증하였다.

후속연구

향후 연구는 다양한 분석 질의를 지원하기 위해 제안하는 기법을 top-k 질의를 지원하는 알고리즘으로 확장하는 것이다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

맵리듀스를 이용한 효율적인 k-NN 조인 질의처리 알고리즘
Efficient k-Nearest Neighbor Join Query Processing Algorithm using MapReduce 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

데이터처리

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

맵리듀스를 이용한 효율적인 k-NN 조인 질의처리 알고리즘 Efficient k-Nearest Neighbor Join Query Processing Algorithm using MapReduce 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

데이터처리

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

맵리듀스를 이용한 효율적인 k-NN 조인 질의처리 알고리즘
Efficient k-Nearest Neighbor Join Query Processing Algorithm using MapReduce 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper