Research Of Spatial Object Approximation Method For Spatial Index Optimization

Spatial index is a kind of data structure which arranged according to a certain order by space object's position and shape or some spatial relationship between spatial objects.It aims to quickly filter spatial objects that are not related to a specific spatial operation.It is an important indicator to ensure the efficiency of efficient searching and displaying spatial data,its performance directly affects the overall performance of geographic information systems and spatial databases.At present,various kinds of spatial index structures have emerged at home and abroad.Although they have optimized spatial indexing algorithms from different aspects,there still are a lot of limitations.Among them,in the index tree's struction,the serious spatial overlap between nodes causes a series of drawbacks such as an increasing the depth of the index tree and multiple query paths in the same spatial query,that will reduce the spatial index quality and affect the spatial index performance.And with the increasing of the complexity of data volume,data types and the continuous updating of index data,such drawbacks have become more apparent.Spatial object approximation has low accuracy and is an important issue that results in a large overlap between index nodes.By using related spatial target approximation techniques(such as the minimum circumscribed rectangle),the spatial relationship calculation of the original spatial target can be reduced,and the spatial query efficiency can be improved.Geographical Information System deals with spatial objects that have irregular geometries(such as roads,rivers,etc.),and if the precise spatial location is directly used to achieve certain given spatial operations(such as intersection,inclusion,etc.),the computational load will increase dramatically.However,most of the existing methods do not consider the geometric features of the space target,which result in a high degree of spatial overlap between the index nodes,and affect the spatial query performance.For the purpose of optimizing the spatial index structure,this paper takes the spatial target approximation technology as entry point,combines the geometric features of line and surface geographic vector elements,proposes a spatial index optimization structure based on geometric Template Approximation(a geometric template is a graphic that roughly approximates the original geometric object in a grid),and designs spatial data retrieval experiments.Experiments show that the spatial index optimization method significantly improves the efficiency and accuracy of window query and spatial join query.The research contents and achievements of this paper are as follows:(1)Geometric templated for two-dimensional spatial index optimizingIn order to solve the problems on the low accuracy of spatial objects and difficulties in balacing the efficiency and space complexity of index trees,this paper proposes a geometric template construction scheme based on multi-level meshing,defines the geometric template structure which is based on grid data structure,and the classification algorithm which improves minimum editing distance and frequency histogram of geometric template,the geometric dictionary bit encoding algorithm which is based on graphical dictionary,and a rough calculation strategy for spatial relations which is based on a mixture of bit manipulation and geometric template spatial relation prefetching.(2)Spatial Index Optimization Method Based on Geometric Template ApproximationSince R*tree is the most widely used class of R-tree variants,this paper uses R*tree as a reference and proposes a spatial index optimization method based on geometric template approximation,which replace the minimum bound rectangles in R*tree with geometric template to optimizating.By comparing and analyzing the differences between the algorithm based on geometric template approximation and other old algorithms which construct spatial index data under the minimum bound rectangles approximation.This paper proposes a window query and spatial join query algorithm based on the initial calculation of the spatial relations of geometric templates.A node splitting algorithm based on geometric template transformation(starting point transformation,level shifting)and bit operation was designed,and an area and perimeter calculation method based on geometric template type and level was constructed.Based on this,a geometric template based approximation was finally proposed.Spatial index construction and deletion algorithms.(3)Design prototype system for experimental verificationBy selecting a representative line and polygon OSM(Open Street Map)vector dataset in China,this paper constructs a prototype system called VGIS,analyzes spatial index optimization method which is based on geometric template approximation from the aspacts of window query efficiency,accuracy,and storage space compression ratio.The results show that the spatial index optimization method based on geometric template approximation adds a small amount of time to build a tree,reduces the time of window query,spatial join query and the storage space occupancy,improves the spatial query performance,space utilization,and expanda the query predicates.