Font Size: a A A

Study On Spatial Index Structure And Spatial Query Algorithm In Supporting System Of Three Resistances

Posted on:2011-07-11Degree:MasterType:Thesis
Country:ChinaCandidate:H Y DingFull Text:PDF
GTID:2178360305977089Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
With rapid development of computer technology and explosion of social needs, spatial information system technology has developed rapidly and its application area is increasingly expanding. The face of massive and complex spatial data makes it an important research area for recent spatial information system to improve the efficiency of querying information. Therefore, setting the supporting system of three resistances as background, the present paper has selected the index structure and query algorithms in the space system as the subject and made the following contributions:1) Improvement of spatial system index. Spatial indexing efficiency is often evaluated by several aspects as the index's storage efficiency, query efficiency and update efficiency. But the truth is that it's difficult to design a spatial index structure in which all the above aspects can be fully fulfilled. Based on the types of spatial data and its functional characteristic, as well as an analysis of the efficiency of each spatial index, the present paper has theoretically constructed a spatial index structure, a Hilbert coding-based fixed grid index, which would be suitable for the supporting system of three resistances. Experiments have showed that this index structure can improve the efficiency of spatial query system and optimize the system performance.2) Design of the construction of the system spatial index algorithm. The design of the construction of the system spatial index algorithm has followed three steps. First, divide the grid. According to the actual situation, the whole map has been divided into two to the 2 N-th power grids. Second, establish the grid index table. In storing index information, the Hilbert code which is generated from the line number and column number would be taken as the exclusive identification for the gird. Third, scan all graphics objects, and remove the coordinates information. Then judge its proper grid and its intersection grids, and finally insert the corresponding index into index files.3) Improvement of the shortest path Dijkstra algorithm. The main drawbacks of Dijkstra algorithm are in the fields of storage structure and the next nearest query node. The present paper mainly made improvements from the following two aspects. One is the improvement of the storage structure. The Hashtable in the framework of JAVA has been employed to compress data storage space. The other is the improvement of the executive efficiency. Only that updating the record of follow-up point's distance is required. In this way, the executive efficiency can be rapidly improved. System only needs the shortest distance between the beginning and the end. In this way the cycling executive times can be reduced, therefore the speed of spatial query can be further accelerated.
Keywords/Search Tags:Spatial Index, Grid Index, Hilbert curve, Dijkstra Algorithm
PDF Full Text Request
Related items