The Study Of Hybrid Spatial Index Based On Vector Approximation

With the continuous development of earth observation method, the human’s ability of obtaining spatial data reaches an unprecedented level. Rapidly and accurately obtaining effective information from the massive spatial data is not only the premise of GIS availability, but also the basis of further analysis and application of spatial data. Hybrid spatial query is a common way of spatial query,geometry and attribute condition to query for spatial information to meet the needs of users. In order to improve the efficiency of the hybrid spatial query, usually by a spatial index and attribute index pruning and merging the results respectively. But due to establishing the index on different fields respectively, on the one hand it increases the complexity of the index maintenance and reduces the storage efficiency; on the other hand it lacerates possible correlation between the features and reduces the query efficiency.This paper proposes a hybrid spatial index. The index is introduced into vector approximation and the spatial extension, pruning geometry and attribute with features’ correlation at the same time, and realizing the high query efficiency and lower storage overhead by means of binary bit vector and efficient computer operation ability. In particular, the index does not need to establish a spatial index structure based on MBR, and it can realize more accurate spatial filtering through the implicit space pruning.The main contents and achievements of this paper are listed as follows:(1)Proposing the spatial extension mechanism of vector approximation. Paper compares and analyzes the balance and non-balance division’s influence law of query efficiency, proposing to establish the optimization scheme of non-balance divide on the geometry and attribute features, and using vector approximation method to mapping multi-dimensional features of spatial data to a one dimensional linear space. The extension mechanism has the advantages of low storage and high query performance.(2)Proposing the vector approximation based hybrid spatial index(VAHSI). The index is based on the spatial vector approximation thought by mapping space dataset into a series of data bucket. In the primary filter layer, based on the counting sequence idea, we set up a spatial dataset and high-speed mapping table of data bucket, and based on this high-speed mapping table we can realize directly positioning of data bucket in the O(1) time without any auxiliary structure; in the secondary index layer, according to the data density of data bucket, we establish a bucket index using a vector and the enumeration method respectively. In the query, we firstly decompose the query conditions and prune through high-speed mapping table, then we perform a second quick pruning by bucket index and bit operation to obtain more refined candidate dataset, finally we filter dataset accurately. Paper gives the query, insert, and delete algorithm of the hybrid spatial index.(3)We built a prototype system based on VAHSI and make a series of comparative experiments. The results show that the proposed hybrid spatial index is high performance and low storage cost.