Title :
HQ-Tree: A distributed spatial index based on Hadoop
Author :
Feng Jun ; Tang Zhixian ; Wei Mian ; Xu Liming
Author_Institution :
Coll. of Comput. & Inf., Hohai Univ., Nanjing, China
Abstract :
In this paper, we propose a novel spatial data index based on Hadoop: HQ-Tree. In HQ-Tree, we use PR QuadTree to solve the problem of poor efficiency in parallel processing, which is caused by data insertion order and space overlapping. For the problem that HDFS cannot support random write, we propose an updating mechanism, called "Copy Write", to support the index update. Additionally, HQ-Tree employs a two-level index caching mechanism to reduce the cost of network transferring and I/O operations. Finally, we develop MapReduce-based algorithms, which are able to significantly enhance the efficiency of index creation and query. Experimental results demonstrate the effectiveness of our methods.
Keywords :
cache storage; database indexing; parallel programming; quadtrees; query processing; HDFS; HQ-Tree; Hadoop; I/O operation cost reduction; MapReduce-based algorithms; PR quadtree; copy write updating mechanism; data insertion order; distributed spatial data index; index creation efficiency enhancement; index update; network transfer operation cost reduction; parallel processing; query efficiency enhancement; random write; space overlapping; two-level index caching mechanism; Algorithm design and analysis; Distributed databases; Partitioning algorithms; Spatial databases; Spatial indexes; Vegetation; hadoop; mapreduce; quadtree; spatial index;
Journal_Title :
Communications, China
DOI :
10.1109/CC.2014.6895392
