空间数据库平面线段快速最近邻查询算法  

Fast Algorithm of Nearest Neighbor Query for Line Segments of Spatial Database

作　　者：刘润涛[1] 郝忠孝[2,3] 

机构地区：[1]哈尔滨理工大学信息与科学计算技术研究所,哈尔滨150080 [2]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [3]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机研究与发展》2011年第12期2379-2384,共6页Journal of Computer Research and Development

基　　金：黑龙江省自然科学基金项目(F200601);黑龙江省教育厅科学技术基金项目(11511027)

摘　　要：给出了线段按其MBR进行排序的定义.以提高线段数据库最近邻查询效率为目标,以此为基础提出了一种线段数据的索引结构——SI-树,规定SI-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行最近邻查询时可以进行快速定位.给出了新的最近邻查询剪枝规则.利用这些规则在进行相应的查询时减少了许多不必要的计算,对节点有效地进行筛选和过滤,加快了查询的速度.实验表明:给出的最近邻查询算法与现有的同类查询算法相比查询效率有较大的提高.The definitions of the orders between line segments are given according to their MBRs. Based on the orders, an index structure—SI-tree for line segments is proposed with the aim of improving the efficiency for nearest neighbor query. In the structure, it is set that the children nodes of each middle node are arranged in some order according to their geometric locations so that the positions of data can be determined quickly when nearest neighbor query is taken on the structure. It is a brand new way to process this kind of problems. Three pruning rules for NN query are created, by which a lot of unnecessary computations can be reduced to achieve effective screening and filtering of data when corresponding query is processed so that the speed of query is quicken. In the pruning rules, the main computing used to make decision to prune a node is judgment, which is simpler than that used in other algorithms of the same kind of problems. A new nearest query algorithm for line segment data set and the proofs of the algorithms＇correctness and termination are presented. The experiments show that the efficiency of query with the new algorithms presented in this paper is greatly improved, compared with that of the current algorithms used to solve the same problems when nearest neighbor query is processed.

关 键 词：线段数据库 最近邻查询 SI-树 序 算法 空间索引 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]