XQ-Index: A Distributed Spatial Index for Cloud Storage Platforms

Currently the cloud storage platforms (CSPs) based on key-value model only support simple keyword-based queries and can't answer complex queries efficiently due to lacking of efficient index techniques. In this paper we propose a novel distributed spatial index (XQ-index) for CSPs to solve this problem. In the process of index building, we proposed a new space partitioning method based on an improved Quad-tree algorithm that can make full use of MapReduce parallel computing model. Our approach can process typical spatial queries including range queries and k-NN queries efficiently based on MapReduce framework. Besides, frequent change of data on big number of machines makes the index maintenance a challenging problem, and to cope with this problem we proposed an index update strategy that can effectively update the index structure. In the experiments, we implement the XQ-index on Hadoop platform to test the effect of parameter on the efficiency of index, and also test the efficiency of index building, querying and updating under data of different sizes. Experiments show that the XQ-index is quite efficient and independent from the underlying infrastructure and can be easily carried over for implementation on various CSPs.