HQ-Tree: A distributed spatial index based on Hadoop
Jun Feng, Zhixian Tang, Mian Wei, Liming Xu · China Communications · 2014
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.