【作者】 刘润涛；

【导师】 郝忠孝；

【作者基本信息】 哈尔滨理工大学 ， 测试计量技术及仪器， 2009， 博士

【摘要】 计算机硬件技术的不断发展为海量数据的处理提供了良好的平台。近年来,空间数据库已成为计算机科学领域的研究热点。它在地理信息系统(GIS)、计算机辅助设计与制造(CAD/CAM)、数字化城市、定位服务等众多领域得到了广泛的应用。空间数据索引技术是空间数据库的核心,它的性能直接决定着整个空间数据管理系统的好坏。研究空间数据索引技术以寻求更好的空间数据索引机制,一直是空间数据库领域的研究热点。因此,对它的研究既具有重要的理论意义又具有广泛的应用价值。本文采用空间目标的最小外包矩形(Minimum Bounding Rectangle)近似表示方法,以获得具有较高性能的空间数据索引结构为目标,通过定义空间目标间的序关系并利用这些序关系对数据空间的划分方法进行探讨。同时,利用定义的空间目标间的序关系研究了区域查询问题、最近邻查询问题、k最近邻查询问题,将其方法进行扩展研究了空间数据库平面线段的最近邻问题。取得了如下的研究结果:对数据空间的二分划分方法进行了深入的研究。建立了划分的优化准则,利用这些准则,分别给出了极小化覆盖和极小化交叠的二分划分方法,并建立了对应划分下的空间索引结构,用实验证明了得到的方法的先进性。对数据空间的四分划分方法进行了深入的研究。建立了划分的极小化交叠的准则,给出了极小化交叠的四分划分方法,并建立了对应划分下的基于四叉树和R-树的空间索引结构,用实验验证了新索引结构中各层上结点间的交叠明显减少。给出了具有相对位置关系的数据空间的四分划分方法。对数据空间的M分划分方法进行了深入的研究。建立了划分规则,给出了对应的空间索引结构、该结构上的区域查询算法。实验证明:利用数据间的有序性在进行区域查询时可得到有效的数据过滤,查询效果得到了很大的提高。以上述研究为基础,给出了一种基于序的空间数据索引结构-MOIS-树。在树中规定每个结点的孩子结点按照其几何位置满足序关系,使得在中间结点中进行查询时可以进行快速定位。给出了全新的区域查询算法。查询算法中,一方面利用结点的有序性建立了有效的两次剪枝规则,使得只需少量的判断运算就可以过滤掉大量的数据,从而提高了查询的效率;另一方面在查询算法中引入查询窗口包含中间结点MBR的检测,对于较大的查询窗口的查询,有效地减少了MOIS-树区域查询算法中大量无效的相交性判断,从另一方面加快了查询速度。建立了最近邻查询的剪枝规则,利用这些规则给出了最近邻查询算法,减少了结点访问的次数,加快了查询的速度。将最近邻查询进行扩展,给出了k最近邻查询的算法。实验表明:本文给出的区域查询算法、最近邻和k最近邻查询算法与现有的同类查询算法相比查询效率有较大的提高。对空间数据库平面线段数据的最近邻问题进行了深入的研究。线段数据用其MBR近似表示。利用定义的空间数据间的序关系,给出了平面线段数据的索引结构-SI-树的定义、SI-树的生成和结点插入算法。给出了最近邻查询的剪枝规则,建立了最近邻查询算法。实验表明:本文给出的最近邻查询算法与现有的同类查询算法相比查询效率有较大幅度的提高。更多还原

【Abstract】 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.更多还原