Research On Spatial Query Technology Based On Parallel Processing

With the rapid growth of spatial data, more and more information is obtained, and the form of data is more diversified. Spatial query is the basic operation of spatial database. It has been widely used in many important fields, including recommendation system, image retrieval and pattern recognition, etc. As the spatial query requires a lot of space calculation operation, the traditional method of serial processing has become a bottleneck in the face of massive data. Therefore, how to properly organize the spatial data to support efficient query processing is becoming more and more important.To solve these problems, this dissertation proposes a parallel spatial query processing algorithm based on Hilbert R-tree within Master-worker framework. Firstly, we pre-process the spatial data set and encode them based on Hilbert curve order. Secondly, we sort and divide the encoded spatial data sets parallel, send the divided data to each host node to fully take advantage of the cluster resources. The algorithm builds the partial spatial index structure on each worker node parallel and then merges the root node of every partial spatial index on the master node. Finally, in order to support range queries and nearest neighbor queries, this dissertation introduces a baseline search algorithm based on the index structure, and proposes a improved search algorithm based on Hilbert R-tree. The improved algorithm uses Hilbert encoding method and Hilbert R-tree’s property to prune the searching space. It reduces the number of data access greatly.This dissertation proves the feasibility of the algorithm through experiments. The performance of space query baseline algorithm and improved algorithm has been compared. The experimental results demonstrate that the improved algorithm can effectively solve large-scale spatial query problem in real data sets.