The Efficient Algorithms for Constructing Enhanced Quadtrees Using MapReduce

Hongyeon KIM  Sungmin KANG  Seokjoo LEE  Jun-Ki MIN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.4   pp.918-926
Publication Date: 2016/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015DAP0005
Type of Manuscript: Special Section PAPER (Special Section on Data Engineering and Information Management)
Category: 
Keyword: 
index,  quadtree,  range query,  MapReduce,  

Full Text: PDF(1.5MB)>>
Buy this Article




Summary: 
MapReduce is considered as the de facto framework for storing and processing massive data due to its fascinating features: simplicity, flexibility, fault tolerance and scalability. However, since the MapReduce framework does not provide an efficient access method to data (i.e., an index), whole data should be retrieved even though a user wants to access a small portion of data. Thus, in this paper, we devise an efficient algorithm constructing quadtrees with MapReduce. Our proposed algorithms reduce the index construction time by utilizing a sampling technique to partition a data set. To improve the query performance, we extend the quadtree construction algorithm in which the adjacent nodes of a quadtree are integrated when the number of points located in the nodes is less than the predefined threshold. Furthermore, we present an effective algorithm for incremental update. Our experimental results show the efficiency of our proposed algorithms in diverse environments.