Research On Order-based Spatial Data Index And Query Algorithms

The continuous development of computer hardware techniques provides a good platform for dealing with mass data of great amount. In recent years, spatial database has become a hot research topic in computer science field. It has found wide applications in many areas such as geographic information system(GIS), computer aided design and manufacture(CAD/CAM), digital city and positioning service. Spatial data index is the kernel of spatial databases. Its properties will have direct and decisive impact on the whole spatial data management systems. To make research on spatial data index to find better index methods has been a hot research topic in the area of spatial databases. Therefore, the research on spatial data indexes has not only important theoretical significance but also wide application values.The approximate expression of minimum bounding rectangle (MBR) for spatial objects is adopted in this dissertation. At the aim of obtaining a spatial index structure with high performance, the partition methods of data spaces are investigated, by defining the order relations between spatial objects and using them. Meanwhile the problems of range query, nearest query and k nearest query are studied by the defined order relations between spatial objects. By generalizing the methods, the nearest neighbor of planar line segments of spatial database is researched. The following research results are achieved:The deep research on binary partition methods of data spaces is made. The optimization criterions of partitioning data spaces are established. With them, the binary partition methods with minimized coverage and minimized overlap are given. And the spatial index structures corresponding to the partition methods are established. Moreover, the advances of new methods are proved experimentally.The deep research on quarter partition methods of data spaces is made. The optimization criterions of partitioning data spaces are established. The quarter partition methods with minimized overlap are given. And the quadtree and R-tree based spatial index structures corresponding to the partition methods are established. It is experimentally proved that the overlap among the nodes on the same level of the new index structure is reduced evidently. The quarter partition methods of data spaces with relative position relations is presented.The research is done on M-partition method of data spaces. The partition rule related to the orders is set up, with which the spatial index structure is created, and the range query algorithm is given. Experiments show that data can be filtered effectively when range query is executed by the orders between data, and the query efficiency is greatly improved.Based on the above-mentioned researches, an order-based spatial index structure-MOIS-tree is proposed. In the tree, it is set that the children nodes of any middle node must be arranged according to their geometric positions to satisfy one of the order relations given above. To do so can make the positions determined quickly when a range query is processed in the middle nodes. The brand new range query algorithm is proposed. The query efficiency is greatly improved in the algorithm in two ways: one is that the effective pruning rule for pruning two times by use of the orders between data objects is established so that a great amount of data can be filtered off just to take a little amount of judgment operations; another is that the the test of query window's containing the middle node's MBR is introduced to reduce a great number of invalid intersection judgment(computations) in the range query algorithm of MOIS-tree to accelerate the query speed. The pruning rules for nearest neighbor query on MOIS-tree is set up, with which nearest query algorithm is given to reduce the number of accessed nodes to speed the query. The nearest query algorithm is generalized to obtain the k nearest neighbor query algorithm. Experiments show that the range query algorithm, the nearest query algorithm and the k nearest neighbor query algorithm have higher query efficiencies than the algorithms of the same types.The deep research is made on the nearest neighbor query of spatial database planar line segments. MBR approximate expression for line segments is adopted here. By using the order relations defined in this dissertation, the definition of the index structure-SI-tree for planar line segments and algorithms of the creation and node insertion of the new index structure are given. The pruning rule for nearest neighbor query is set up, with which the nearest neighbor query algorithm is proposed. Experiment shows that the query efficiency is improved greater with the algorithm in this dissertation than the existing ones of the same types.