Enhanced R-tree Bulk Loading Scheme Using Map-Reduce Framework

Abstract

An R-tree is an index structure that enables fast accesses to multi-dimensional data. Constructing an R-tree for a given data set yields an efficient R-tree structure than incrementally building one as data are inserted. However it usually takes a lot of time constructing an R-tree for a huge volume of data. In this paper, we propose a parallel R-Tree construction scheme based on a Hadoop framework. The proposed scheme divides the data into partitions, builds local R-trees in parallel, and merges them to construct an R-tree that covers whole data set. While generating the partitions, it considers the data distribution so that each partitions have nearly equal amount of data. Therefore the proposed scheme gives an efficient index structure while reducing the construction tim