[논문]맵리듀스 기반 kNN join 질의처리 알고리즘의 설계 및 성능평가

김태훈; 이현조; 장재우

문제 정의

본 논문에서는 대용량 데이터 분석을 위한 맵리듀스 기반 kNN join 질의처리 알고리즘을 제안하였다. 제안하는 질의처리 알고리즘은 시드 기반의 동적 분할을 수행하여 색인구조 구축비용을 감소시킨다.
이러한 문제점을 해결하기 위해, 본 논문에서는 대용량데이터 분석을 위한 맵리듀스 기반 kNN join 질의처리 알고리즘을 제안한다. 제안하는 질의처리 알고리즘은 시드 기반의 동적 분할을 통해 색인구조 구축비용을 감소시킨다.
또한 kNN 질의 처리를 위한 후보 영역 선정 시 k값에 비례하여 후보영역의 크기가 증가하기 때문에, kNN 연산 오버헤드가 증가하는 문제점이 존재한다. 이를 해결하기 위해 본 논문에서는 대용량 데이터 분석을 위한 맵리듀스 기반 kNN join 질의처리 알고리즘을 제안한다. 제안하는 질의처리 알고리즘은 시드 기반의 동적 분할을 통해 색인구조 구축비용을 감소시킨다.

제안 방법

둘째, 1단계 맵리듀스 단계에서는 질의 처리 연산량을 감소시키기 위해, 구축한 보로노이 다이어그램을 기반으로 데이터와 모든 피봇간의 거리를 측정하여 가장 가까운 피봇(Pi)을 선정하고, 선정된 피봇에서 가장 인접한 데이터 (ri)를 포함시켜 데이터 분할을 수행한다. 이때, 효율적인 kNN 탐색을 지원하기 위해, 데이터 집합 R과 S에 대한 셀별 통계 정보(Partition Statics)를 측정한다.
제안하는 기법은 질의 후보 영역 내에 포함된 S의 시드 수(=Sj의 수)가 전체 S의 2% 이상이면 100% 질의 정확도를 나타낸다. 따라서 이를 바탕으로 제안하는 기법은 전체 시드의 2% 이상의 S 시드를 포함하도록 질의처리 후보 영역 탐색 범위를 설정한다.
이는 기존 기법의 경우, kNN질의 처리를 위한 후보 영역 선정 시 k값에 비례하여 후보 영역의 크기가 증가하기 때문에, kNN join 연산 오버헤드가 증가하여 질의 처리 시간이 증가됨을 나타낸다. 반면, 제안하는 기법은 후보 영역을 시드간 평균 거리를 기반으로 질의 처리 후보 영역을 선정하여 kNN 탐색 시 필터링을 수행하기 때문에, kNN 연산 오버헤드를 감소시킨다.
선정된 후보 집합들은 kNN-join 탐색 후보 영역을 바탕으로 개별 데이터의 분할을 수행한다. 첫째, 집합 日에 속한 데이터「의 경우, 가장 인접한 시드 Ri를 탐색하여 해당 데이터 집합에 포함시킨다.
실험 환경은<표 1>과 같다. 성능 평가 측정을 위해, 2차원 데이터 60만개씩을 포함하는 두 개의 데이터 집합 R, S를 생성하고 k는 20, 40, 60, 80, 100, 추출된 피봇/ 시드 수는 2000으로 고정하고 성능을 측정하였다. 이때 성능에 수행된 실험은 5번 반복하여 평균값을 측정하였다.
제안하는 질의처리 알고리즘은 시드 기반의 동적 분할을 수행하여 색인구조 구축비용을 감소시킨다. 아울러 시드간 산술 평균 거리를 기반으로 질의 처리 후보 영역을 선정함으로써, kNN join 질의를 위한 연산 오버헤드를 감소시킨다. 마지막으로 기존기법과 성능 평가를 수행하여, 질의처리 시간 및 정확도 측면에서 기존 기법에 비해 우수함을 검증하였다.
피봇 추출 알고리즘은, i) Random Selection, ii) Farthest Selection ⅲ) k-means Selection 이 존재하며, 데이터의 특성을 고려하여 알고리즘을 선택, 수행한다. 아울러, 추출된 피봇 데이터를 바탕으로 각 데이터 집합별로 보로노이 다이어그램을 구축한다. 이때, 각 셀에 대해, <셀 ID, 피봇ID, 피봇의좌표(X, y), 경계점의 좌표 집합>의 정보를 저장하는 셀 정보 테이블을 생성한다.
포함시켜 데이터 분할을 수행한다. 이때, 효율적인 kNN 탐색을 지원하기 위해, 데이터 집합 R과 S에 대한 셀별 통계 정보(Partition Statics)를 측정한다. 셀별 통계정보는 보로노이 셀에 포함되는 데이터의 수(# of objects in PiR), 피봇과의 최소/최대 거리 (Lower Bound(PiR), Upper Bound(PiR)), k개의 인접한 파티션의 집합(Pi, Si .
따라서 후보 집합 선정 비용 및 후보 집합 크기에 따른 질의처리 성능 사이의 trade-off 관계를 고려하여 초기 탐색 범위를 설정하는 것이 필요하다. 이를 위해 본 논문에서는 후보 영역 탐색 비용을 감소시키기 위해, k개의 시드를 포함하는 평균 거리를 초기 탐색 범위로 설정한다. 이를 통해, 후보 집합 탐색 시 한번의 탐색으로 약 k개의 이웃한 다른 시드를 탐색할 확률을 향상시킨다.
감소시킨다. 이를 위해, i) 저장된 셀별 통계정보를 바탕으로 日의 부분집합 Ri에 대하여 가장 가까운 S의 부분집합 Sj를 후보영역 탐색 집합으로 선정한다. 이때, Sj의 수는 k값과 동일하며, 후보의 거리는 Ri의 피봇-데이터 최대거리, Sj의 피봇-데이터 최대거리, , :Ri와 Sj의 피봇간 거리의 총합으로 계산된다.
필수적이다. 이를 위해, 제안하는 기법의 탐색범위 설정에 대한 실험을 수행하였다.<표 2>는 k=100일 때, 제안하는 기법의 후보 영역 크기에 따른 질의 결과 정확도를 나타낸다.
제안하는 질의처리 알고리즘은 시드 기반의 동적 분할을 수행하여 색인구조 구축비용을 감소시킨다. 아울러 시드간 산술 평균 거리를 기반으로 질의 처리 후보 영역을 선정함으로써, kNN join 질의를 위한 연산 오버헤드를 감소시킨다.
이를 해결하기 위해 본 논문에서는 대용량 데이터 분석을 위한 맵리듀스 기반 kNN join 질의처리 알고리즘을 제안한다. 제안하는 질의처리 알고리즘은 시드 기반의 동적 분할을 통해 색인구조 구축비용을 감소시킨다. 또한 시드 간 평균 거리를 기반으로 질의 처리 후보 영역을 선정함으로써, kNN-join 질의를 위한 연산 오버헤드를 감소시킨다.

대상 데이터

日의 시드 Ri에 대해 kNN-join 후보 영역 탐색을 위해, Ri의 초기 탐색 범위를 확장하여 전체 시드 수의 m%에해당하는 가까운 S의 시드 Sj들을 후보 집합으로 선정한다. 데이터 집합 S에 대해 시드 추출 수가 n(Seed), 전체 데이터 수가 n(S), 후보 집합에서 포함하는 시드 수가 m%일 때, 후보 집합에 포함되는 평균 데이터의 수는( n(Candidate)) 식 (2)과 같다.

데이터처리

본 장에서는 제안하는 kNN join 질의처리 알고리즘의 우수성을 검증하기 위하여 성능 평가를 수행한다. 성능 평가를 위해 제안하는 kNN join 질의 처리 알고리즘 및 기존 보로노이 기반 질의처리 알고리즘(VkNN-join)[기을 비교한다.
검증하기 위하여 성능 평가를 수행한다. 성능 평가를 위해 제안하는 kNN join 질의 처리 알고리즘 및 기존 보로노이 기반 질의처리 알고리즘(VkNN-join)[기을 비교한다. 실험 환경은<표 1>과 같다.
이때 성능에 수행된 실험은 5번 반복하여 평균값을 측정하였다. 아울러 kNN join 질의처리에 대한 신뢰도를 검증하기 위해, 제안하는 시드 기반 질의 처리 알고리즘의 정확도를 평가하였다.
성능 평가 측정을 위해, 2차원 데이터 60만개씩을 포함하는 두 개의 데이터 집합 R, S를 생성하고 k는 20, 40, 60, 80, 100, 추출된 피봇/ 시드 수는 2000으로 고정하고 성능을 측정하였다. 이때 성능에 수행된 실험은 5번 반복하여 평균값을 측정하였다. 아울러 kNN join 질의처리에 대한 신뢰도를 검증하기 위해, 제안하는 시드 기반 질의 처리 알고리즘의 정확도를 평가하였다.

이론/모형

이를 위해 전처리 단계에서는 임의 선정(Random Selection) 알고리즘을 이용하여 시드를 선정하고, kNN join 질의처리를 위한 후보 영역 탐색시 사용되는 초기 탐색 범위를 설정한다. 이때, 후보 집합 선정을 위한 시드별 초기 탐색 범위의 크기가 크게 설정될 경우, kNN 탐색 후보 내에 포함되는 후보 수가 증가하기 때문에, 데이터전송 오버헤드 및 kNN 탐색 비용이 증가한다.

성능/효과

아울러 시드간 산술 평균 거리를 기반으로 질의 처리 후보 영역을 선정함으로써, kNN join 질의를 위한 연산 오버헤드를 감소시킨다. 마지막으로 기존기법과 성능 평가를 수행하여, 질의처리 시간 및 정확도 측면에서 기존 기법에 비해 우수함을 검증하였다.
질의처리 성능평가를 나타낸다. 성능평가 결과 제안하는 알고리즘은 질의 처리 시간 측면에서 기존 기법에 비하여 약 1.9배의 성능 향상을 나타낸다. 이는 기존 기법의 경우, kNN질의 처리를 위한 후보 영역 선정 시 k값에 비례하여 후보 영역의 크기가 증가하기 때문에, kNN join 연산 오버헤드가 증가하여 질의 처리 시간이 증가됨을 나타낸다.
또한 시드 간 평균 거리를 기반으로 질의 처리 후보 영역을 선정함으로써, kNN-join 질의를 위한 연산 오버헤드를 감소시킨다. 아울러, 성능 평가를 통해 제안하는 기법이 질의처리 시간 측면에서 기존 기법에 비해 우수함을 나타낸다.
<표 2>는 k=100일 때, 제안하는 기법의 후보 영역 크기에 따른 질의 결과 정확도를 나타낸다. 제안하는 기법은 질의 후보 영역 내에 포함된 S의 시드 수(=Sj의 수)가 전체 S의 2% 이상이면 100% 질의 정확도를 나타낸다. 따라서 이를 바탕으로 제안하는 기법은 전체 시드의 2% 이상의 S 시드를 포함하도록 질의처리 후보 영역 탐색 범위를 설정한다.

후속연구

향후 연구로는 제안하는 기법의 질의 처리 성능 및 정확도에 대한 trade-off을 실험하여, 정확도에 따른 질의처리 성능을 분석하는 것이다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

[국내논문] 맵리듀스 기반 kNN join 질의처리 알고리즘의 설계 및 성능평가
Design and Performance Analysis of MapReduce-based kNN join Query Processing Algorithm 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

연합인증

[국내논문] 맵리듀스 기반 kNN join 질의처리 알고리즘의 설계 및 성능평가 Design and Performance Analysis of MapReduce-based kNN join Query Processing Algorithm 원문보기

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

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

문제 정의

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

[국내논문] 맵리듀스 기반 kNN join 질의처리 알고리즘의 설계 및 성능평가
Design and Performance Analysis of MapReduce-based kNN join Query Processing Algorithm 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper