【作者】 杨泽雪；

【导师】 郝忠孝；

【作者基本信息】 哈尔滨理工大学 ， 计算机应用技术， 2014， 博士

【摘要】 随着空间数据库在地理信息系统(GIS)、卫星图像数据处理系统、计算机辅助设计与制造(CAD/CAM)、多媒体系统等领域的广泛应用，作为空间数据库中的核心问题的空间查询已成为空间数据库的重点研究问题。查询效率是衡量空间数据库性能的重要指标，在许多实际应用中对各种空间查询提出了迫切的要求，空间查询的性能是这些应用成功的关键。空间连接查询和最近邻查询是空间查询中的重要查询，研究新的算法用以提高这两种查询的效率对空间查询具有重要意义。本文对空间连接查询和最近邻的变体查询进行研究，主要的工作可概括为以下5点：1.针对限定范围内的空间连接查询问题进行研究，提出受限空间连接查询的概念，分析该查询的特征，给出两个直接处理方法，并给出基于R-tree的受限空间连接算法。利用混合索引结构QR-tree的优良特性，提出基于QR-tree的受限空间连接查询算法，该方法既能避免R-tree的节点重复，又能克服四叉树较大的存储代价，解决了空间连接查询代价昂贵的问题。对算法的查询代价进行分析和比较，理论和实验证明算法具有较高的查询效率。2.针对障碍物环境中的反向最近邻查询进行研究，提出基于障碍距离的反向最近邻查询的新变体，即障碍反向最近邻查询，给定查询数据集及障碍集和查询点，障碍反向最近邻查询找到查询数据集中以查询点为障碍最近邻的点，给出障碍反向最近邻查询的过滤-精炼算法，通过实验证明所提的算法具有较高效率。3.针对障碍物环境中的组最近邻查询进行研究，提出基于障碍距离的组最近邻查询的新变体，即组障碍最近邻查询，即查找数据集中距离一组对象的障碍距离之和最小的点。根据点与查询点集的MBR之间的位置关系，构造各种情况下的剪枝区域。利用剪枝区域对障碍集进行剪枝，给出点与查询点集之间的障碍距离计算算法。定义组障碍最近邻查询的剪枝规则，结合障碍距离计算算法给出组障碍最近邻查询算法。通过实验证明所提的算法具有较高效率。4.针对动态环境中的连续反向最近邻查询进行研究，按照单色和双色两种情况，分别给出基于Voronoi图的连续单色和连续双色反向最近邻查询算法，算法按照移动点Voronoi图的拓扑结构是否改变分为两种情况，分别给出每种情况对应的解决方法。提出障碍环境中连续反向最近邻查询的新变体，即连续可视反向最近邻查询，找到数据集中将查询线段作为可视最近邻的点，利用线段的可视性判断和相应的剪枝规则，提出连续可视反向最近邻查询的算法及相关定理和证明。实验证明，算法具有较高的查询效率。5.针对平面线段的空间查询进行研究，提出线段最近对查询，即查找两个线段集中距离最小的线段对，提出基于Voronoi图的线段最近对查询算法，算法分别建立两个线段集的Voronoi图，利用Voronoi图的优良特性找到结果。对平面线段的反向最近邻查询进行研究，提出基于Voronoi图的线段反向最近邻查询算法，根据查询线段与线段集是否相交两种情况进行研究，分别给出相应的处理方法。实验证明所提的算法具有较高效率。更多还原

【Abstract】 With a wide range of applications for spatial database in GeographicInformation Systems(GIS), satellite image data processing systems, Computer-Aided Design and Manufacturing(CAD/CAM), and multimedia systems, spatialquery as the core problem of spatial database has become the research focus. Theefficiency of spatial query is an important indicator to measure the performanceof spatial database. The urgent requirements have been put on various spatialqueries in many practical applications. Spatial query performance is critical tothe success of these applications. Spatial join and nearest neighbor query areimportant queries of spatial queries. Research on new algorithms to improve theefficiency of these two queries is important for spatial queries. In this paper,spatial join and nearest neighbor variants query are studied, the main work can besummarized as the following five points:Firstly, the problem of spatial join query within the constrained range isstudied, and the concept of constrained spatial join query is put forward. Thecharacteristic of this query is analyzed. Two direct approachs and constrainedspatial join algorithm based on R-tree are given.By using of the goodcharacteristics of the hybrid spatial index structure QR-tree, the constrainedspatial join algorithm based on QR-tree is proposed. The method can not onlyavoid R-tree node duplication, but also overcome the large storage costs ofquadtree and solve the expensive cost problem for spatial join query. Query costof the algorithm is analyzed and compared. Theory and experiment prove that thealgorithm has high search efficiency.Secondly, the problem of reverse nearest neighbor query in obstacleenvironments is studied. A new variant of the reverse nearest neighbor querybased on obstructed distances is put forward, that is, obstructed reverse nearestneighbor query. Given an obstacle set, a data set, and a query point, obstructedreverse nearest neighbor query finds out the points in data set which take the query point as obstructed nearest neighbor. The filter and refinement two-stepalgorithm for obstructed reverse nearest neighbor query is raised. Experimentsprove that the proposed algorithm has high efficiency.Thirdly, the problem of group nearest neighbor query in obstacleenvironments is studied. A new variant of the group nearest neighbor query basedon obstructed distances is put forward, that is, group obstacle nearest neighborquery. It finds the point of data set with the smallest sum of obstructed distancesto all points in query data set. According to the positional relationship betweenthe point and MBR of query point set, the pruning region in variouscircumstances is constructed.By using of the pruning region,the obstacle set ispruned. And the obstructed distance calculation algorithm between the point andquery data set is put forward.The pruning rules of group obstacle nearestneighbor query are defined and group obstacle nearest neighbor query algorithmis given combined with the obstructed distance calculation algorithm.Experiments show that algorithms have higher query efficiency.Fourthly, the problem of continuous reverse nearest neighbor query indynamic environments is studied. Continuous monochromatic reverse nearestneighbor and continuous bichromatic reverse nearest neighbor are researched.Continuous reverse nearest neighbor query algorithms based on the Voronoidiagram are araised,and the relevant theorem and proof are given. According towhether change in the topology of the Voronoi diagram of moving points, it hastwo categories:change and no change.Corresponding solutions are given in eachcategory. A new variant of continuous reverse nearest neighbor query in obstacleenvironments is put forward, that is, continuous visible reverse nearest neighborquery. That finds out the points in data set which take the query line segment asvisible nearest neighbor. Through the visibility judgment of query line segmentand the corresponding pruning rules continuous visible reverse nearest neighborquery algorithms is proposed and related theorems and proofs are given.Experiments show that algorithms have higher query efficiency.Fifthly, the problem of spatial queries based on plane line segment is studied.The line segment closest pair query is proposed. That finds the line segment pairwhich have the shortest distance among all the pairs of two line segment sets.The line segment closest pair query algorithm based on Voronoi diagram is put forward. The Voronoi diagram of two line segment sets is construstedrespectively in this method. By making use of the good properties the result isfinded. The line segment reverse nearest neighbor query is researched. The linesegment reverse nearest neighbor query algorithm based on Voronoi diagram isproposed. According to whether two line segments are intersected,it has twocategories:intersected and no intersected. Corresponding solutions are given ineach category. Experiments demonstrate the proposed algorithms have high queryefficiency.更多还原