A GIS Spatial Indexing Approach Based on Hilbert Ordering Code

Raster grid based indexing takes important role in spatial querying. Since spatial ordering based on one dimensional mapping for multi-dimensional data has its own merits, the spatial clustering characteristics of Morton code，Gray code，Hilbert code and Sierpinsky code are analyzed and compared. A conclusion is drawn that Hilbert code is the most efficient mapping scheme for spatial querying. Taking into consideration the characteristics of data models of feature based geographical information system and giving major attention to memory indexing, the authors set forward a dynamic indexing structure for point features based on Hilbert spatial ordering code with binary balanced ordering tree, and an indexing structure for line features based on vertex retrospection. Application of the indexing structures for spatial querying in geographical information system is illustrated.