Research On Spatial Data Index And Query Technology Based On GPU

In recent years,with the rapid popularization of a series of location-based terminal devices such as smartphones and on-vehicle positioning devices,large-scale spatial location information has been generated globally every year,and applications based on location services are closely related to people's daily life.Spatial data has the characteristics of large data volumes,various representation forms,and complex processing procedure.Therefore,to meet the requirements of location services application,it is of great importance to handle large-scale spatial data effectively.At present,most researches on Spatial Data Processing Technology are mainly divided into two categories: One is to improve spatial data processing algorithms under the CPU platform;the other is to improve spatial data processing capabilities by using distributed systems.However,the traditional serial CPU-based spatial data processing technology has gradually exhibited performance shortcomings in the face of increasing spatial data.Compared with the traditional CPU,Graphics Processor Unit(GPU)has powerful multi-core parallel computing capabilities.Rapidly developing general-purpose computing GPU technology and CUDA programming framework,provide a new approach for Spatial Indexing Technology and Spatial Query Technology.Based on GPU technology,this paper has conducted a depth research on spatial data index construction technology and spatial query technology.The main constributions of this thesis are as follows:Firstly,a CUDA-based static R-tree index construction method is proposed.The self-built linear index structure based on the structure of array is used in this method,and the analysis of the parallel algorithm implementation for the traditional static R-tree construction method is completed.For the characteristics of GPU shared memory resources,a two-phase index construction method is adopted in the construction method,which can effectively utilize the high-speed read and write capabilities of shared memory resources.Secondly,on the basis of the self-built static R-tree index,a CUDA-based spatial range query method is proposed,which is mainly to perform GPU parallel design in the fine-filtering phase of range query.In order to solve the problem of low efficiency of the coarse filtering stage in the range query,a range query method for GPU platform based on Geohash grid is further proposed through using Geohash grid to divide the geographical space.Thirdly,based on the two range query methods proposed in this thesis,using the method of converting k-nearest neighbor queries into multiple range queries,the CUDA-based knearest neighbor query method and Geohash grid-based k nearest neighbor query method are proposed respectively.In order to improve the query efficiency,the dynamic expansion strategy of the expansion box in the k-nearest neighbor query method is proposed.Finally,considering that the efficiency of the k-nearest neighbor query is constrained by the range query method,the approximate k-nearest neighbor query method G-Ak NN based on CUDA is proposed by using the spatial adjacency of Geohash coding.And an extended search strategy based on the adjacency of Geohash encoding is given to reduce the error of the query result.Combined with the experimental results of this thesis,we can see that compared to the traditional CPU methods,the CUDA-based static R-tree index construction method and the corresponding spatial query method have significant efficiency improvements and can effectively meet the application requirements in large-scale geospatial data scenarios.