A MapReduce-based Efficient H-bucket PMR Quadtree Spatial Index
Hari Singh, Seema Bawa · 2017
Majority of the MapReduce-Hadoop based indexes are based on either non-disjoint decomposition or the data-dependent disjoint decomposition of space. Quadtree index based regular disjoint decomposition in MapReduce takes different forms of spatial data as point data. Lines, curves, polygons and other higher dimensional data are transformed to point data through a mapping process. Though, the mapping makes index-building quite easy, but it is not suitable for answering search queries. This paper proposes H-bucket PMR Quadtree, a parallel implementation of the existing bucket-PMR Quadtree to handle curvilinear or polygonal map data, in MapReduce. The proposed index uses a two-level of indexing: a global index that indexes the decomposed dataset among cluster nodes to support parallel index building and a local bucket-PMR Quadtree index maintained by each participating cluster node. The proposed index is compared with the state-of-the-art MapReduce based R+-tree indexing and the default key-value storage (non-indexed) Hadoop towards index build-time and spatial queries, such as line search and range search queries. The experimental results demonstrate the effectiveness of the proposed index in MapReduce environment.