빅 데이터를 위한 맵리듀스 프레임워크 기반의 효율적인 쿼드 트리 생성 기법 = An Efficient Quad Tree Construction Method based on MapReduce Frameworks for Big Data

국문 초록 (Abstract)

소셜 네트워크, 센서 네트워크 등의 다양한 기술의 발전으로 처리하는 데이터의 양은 매우 빠르게 급증하고 있으며 따라서 이러한 대용량 데이터를 복수 개의 컴퓨터들로 구성된 군집(cluster)을 활용해 처리하고자 맵리듀스 프레임워크가 구글에서 제안되었다. 그러나 기존의 데이터 처리 기법들은 맵리듀스 프레임워크에 바로 적용할 수 없으므로 다양한 분야에서 맵리듀스 프레임워크에 적합한 새로운 알고리즘이 개발되고 있다. 본 논문에서는 대용량 데이터에 대한 효율적인 접근을 지원하기 위한 색인 구조의 하나인 쿼드 트리를 맵리듀스 프레임워크를 활용하여 구축하고자 한다. 본 제안 기법은 샘플링 기법을 이용하여 데이터를 균등하게 분할함으로써 구축시간을 단축시킨다. 또한 생성된 쿼드 트리와 맵리듀스를 함께 활용하면 맵리듀스 프레임워크만을 사용하는 것 보다 효율적으로 데이터들을 접근할 수 있음을 실험을 통하여 보였다.

다국어 초록 (Multilingual Abstract)

Currently, due to advances of various technologies such as social networks and sensor networks, the size of data has extremely increased, and hence, Google proposed a MapReduce framework which is working on a cluster consisting of connected commodity computers to process big data efficiently. However, since the conventional data processing techniques cannot be directly applied to MapReduce frameworks, many algorithms have been re-developed on MapReduce frameworks. In this paper, we construct a quad-tree index with MapReduce frameworks to support efficient access to big data. Our technique reduces the index construction time utilizing a sampling technique to partition a data set evenly. Additionally, in our experiment, we show the efficiency of data access using our constructed quad tree and MapReduce frameworks together compared to data accessing using MapReduce frame works only.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 배경지식
• 3. 맵리듀스를 이용한 쿼드 트리 구축
• 4. 쿼드 트리를 이용한 맵리듀스 기반의 데이터 접근
• 5. 성능 평가
• 6. 관련 연구
• 7. 결론
• 참고문헌

참고문헌 (Reference)

1 A. Akdogan, "Voronoi-Based Geospatial Query Processing with MapReduce" 2010

2 Z. Liu, "Spatial Quries Evaluation with MapReduce" 2009

3 "Reservoir-sampling algorithms of time complexity O(n(1+log(N/n)))" 20 (20): 481-493, 1994

4 R. A. Finkel, "Quad trees a data structure for retrieval on composite keys" 4 (4): 1-9, 1974

5 S. W. Schlosser, "Materialized community ground models for large- scale earthquake simulation" 2008

6 J. Dean, "MapReduce: Simplified data processing on large cluster" 137-150, 2004

7 C. Xia, "GORDER: An Efficient Method for KNN Join Processing"

8 A. Cary, "Experiences on Processing Spatial Data with MapReduce" 2009

9 W. Lu, "Efficient Processing of k Nearest Neighbor Joins using MapReduce" 5 (5): 2012

10 A. Thusoo, "Data warehousing and analytics infrastructure at Facebook" 2010

11 J. Jestes, "Building Wavelet Histograms on large Data in MapReduce" 5 (5): 2012

12 X. Wu, "Automatic alignment of large-scale aerial rasters to road-maps" (17) :

13 "Apache hadoop" Apache

14 K. Wang, "Accelerating Spatial Data Processing with MapReduce" 2010