Spatial Indices Based on Grid Partition

Based on the fundamental regular grid spatial index, the paper analyzes its advantages and disadvantages, discusses the principles of algorithm improvement based on grid partition, and designs the steps of implementation for each searching algorithm for regional query applications. The time and space complexity of these algorithm improvements are analyzed in detail, and their advantages and disadvantages are presented. Finally, based on practical map data, these searching algorithms are programmed. Experimental results show that for use in region query, analyses in theory accords well with practical applications, and time complexity of every algorithm improvement does not exceed O(N).