Optimization Study Of Quick Neighbourhood Query Algorithm Based On Linear Quadtree

With the deepening of research on Geographic Information System, Location-based services system has been developed and applicated more and more extensively. With the inherent mass and complexity of space data, which makes traditional database query technology increasingly difficult to play its proper role, spatial data query technology need to be developed and innovated urgently. The enormous and complication of spatial data shows that the decisive factor of pros and cons about database performance is in the efficiency of queries. Today's popular neighborhood query methods mostly abstract known object with the investigated object into the space of a point or a rectangular region in order to simplify the irregular nature of the physical shape about the actual object. The linear quadtree-based fast-neighbor query technology has been researched based on this. As the method is still in a state of constant development, there is still much room for the efficiency to be improved.For the deficiencies of the current linear quadtree-based fast-neighbor query algorithm, improvements are maked in the following aspects. Firstlty, the corresponding property value are given to each node, thereby the storage space of the node state list is Omitted, also the mutual access time between the quadtree and grid areas; Secondly, the traditional storage concepts of the tree structure is abandoned, the grid region is stored in main memory directly, which maks the structure more clear, easy to understand; Finally, through the additional level property values, the complex process in finding the adjacent nodes with recursively traverse in the original algorithm is ommited in the query process, which greatly improved the query efficiency of the original algorithm.At the end of the paper, theory, calculation and examples are combined, which powerfully proofs the effectiveness and superiority of the improved algorithm.