基于R-树的最近邻查询研究-韩冬柏.doc

理学硕士学位论文 基于 R 树的最近邻查询研究 韩冬柏 哈尔滨理工大学 2011 年 3 月 国内图书分类号 TP391 理学硕士学位论文 基于 R 树的最近邻查询研究 硕 士 研究生 韩冬柏 导 师 刘润涛 申请学位级别 理学硕士 学 科 专 业 应用数学 所 在 单 位 应用科学学院 答 辩 日 期 2011 年 3 月 授予学位单位 哈尔滨理工大学 Classified Index TP391 Dissertation for the Master Degree in Science Research on Nearest Neighbor Query Based on R Tree Candidate Han Dongbai Supervisor Liu Runtao Academic Degree Applied for Master of Natural Science Speciality Applied Mathematics Date of Oral Examination March 2011 University Harbin University of Science and Technology 哈尔滨理工大学硕士学位论文原创性声明哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明 此处所提交的硕士学位论文 基于 R 树的最近邻查询研究 是本人在导师指导下 在哈尔滨理工大学攻读硕士学位期间独立进行研究工 作所取得的成果 据本人所知 论文中除已注明部分外不包含他人已发表或撰 写过的研究成果 对本文研究工作做出贡献的个人和集体 均已在文中以明确 方式注明 本声明的法律结果将完全由本人承担 作者签名 韩冬柏 日期 2011 年 3 月 23 日 哈尔滨理工大学硕士学位论文使用授权书哈尔滨理工大学硕士学位论文使用授权书 基于 R 树的最近邻查询研究 系本人在哈尔滨理工大学攻读硕士学位期 间在导师指导下完成的硕士学位论文 本论文的研究成果归哈尔滨理工大学所 有 本论文的研究内容不得以其它单位的名义发表 本人完全了解哈尔滨理工 大学关于保存 使用学位论文的规定 同意学校保留并向有关部门提交论文和 电子版本 允许论文被查阅和借阅 本人授权哈尔滨理工大学可以采用影印 缩印或其他复制手段保存论文 可以公布论文的全部或部分内容 本学位论文属于 保密 在 年解密后适用授权书 不保密 请在以上相应方框内打 作者签名 韩冬柏 日期 2011 年 3 月 23 日 导师签名 刘润涛 日期 2011 年 3 月 23 日 哈尔滨理工大学理学硕士学位论文 I 基于 R 树的空间最近邻查询研究 摘 要 最近邻查询是空间数据查询领域中最重要的查询技术之一 在地理信息系 统 GIS 计算机辅助设计与制造 CAD CAM 智能识别系统 多媒体的 应用等各个方面都有广泛的应用 同时随着科学技术的快速发展 对最近邻查 询的效率的要求也越来越高 本文从研究最常用的空间索引技术 R 树出发 对 R 树的查找算法 插入算法 删除算法等进行了探讨 给出了相应的伪代码 并运用相关的性质对 R 树的各种算法过程进行优化 本文研究的是最近邻查询中两个应用较广泛的方面 K 最近邻 KNN 查 询和障碍最近邻查询 ONN 在 KNN 中我们研究了静态的 K 最近邻查询和 动态的 K 最近邻查询 并给出了相应的算法 伪代码和算法解释 然后我们把 空间数据索引技术 R 树应用到 KNN 的查询算法中 运用最小距离 MINDIST 和最大最小距离 MINMAXDIST 来对 R 树的结点进行排序和剪 枝 建立了用于查询的剪枝规则 并给出了基于 R 树的 K 最近邻查询算法 给出了剪枝过程的策略和算法的伪代码 在对障碍最近邻的研究中 把实际应用中的障碍看作多边形 并给出了求 解多边形可视点的算法 然后只需考虑障碍多边形的可视点 过滤掉了大部分 障碍点 再运用 R 树的查询知识对这些可视点进行分类 并求出其最短路径 所得的最短路径就是所求的点与点之间的障碍距离 关键词 空间数据库 R 树 K 最近邻 障碍最近邻 哈尔滨理工大学理学硕士学位论文 II Research on Nearest Neighbor Query Based on R Tree Abstract Nearest neighbor query is one of the most important queries in the space database query techniques It is widely used in many fields such as the geographical information system GIS computer aided design and manufacturing CAD CAM intelligent identification system and multimedia applications etc At the same time with the rapid development of science and technology the requirements to the nearest query efficiency go higher and higher Beginning with studing R trees which is the most commonly used in spatial index technology the search algorithm node insertion algorithm and node deletion algorithm are discussed on R trees And the corresponding pseudo codes are given And by using the related properties of R trees different algorithm processes of R trees are optimized The study of this thesis is related to two aspects of the nearest neighbor queries applied most widely in practice K nearest neighbor query KNN and obstacle nearest neighbor query ONN In KNN we studied static K nearest neighbor search and dynamic K nearest neighbor query and the corresponding algorithms pseudo code and the explanation of algorithm are presented Then we apply the spatial data index technicque R trees to the K nearest neighbor By using the minimum distance MINDIST and maximum minimum distance MINMAXDIST to prune and sort the nodes of R trees during the query is processed the pruning rules are set up for the query Based on those the KNN query algorithm on R tree is given and corresponding pseudo codes In researching the nearest neighbor of obstacles we take the actual application of obstacles as polygons And the algorithm of determining visible points for polygons is presented And then we only need to consider visible points of the obstacle polygons there will be a great amount of obstacles spots to be screened out Moreover by using the query knowledge of R trees to classify the visible points and 哈尔滨理工大学理学硕士学位论文 III to find out the shortest path The shortest path is the obstacle distance between prayer points Keywords spatial database R tree KNN ONN 哈尔滨理工大学理学硕士学位论文 目 录 摘 要 I Abstract II 第 1 章 绪论 1 1 1 研究的目的与意义 1 1 2 国内外研究现状分析 2 1 2 1 基于 R 树的空间索引现状 2 1 2 2 最近邻查询现状 2 1 3 课题来源 4 1 4 本文主要研究内容 4 第 2 章 空间数据库索引 R 树 5 2 1 R 树的定义 5 2 2 R 树的相关算法 7 2 2 1 R 树的查找算法 7 2 2 2 R 树的插入算法 8 2 2 3 R 树的删除算法 10 2 2 4 R 树的算法总结 11 2 3 R 树索引的优化 11 2 4 本章小结 12 第 3 章 基于 R 树的 K 最近邻查询 13 3 1 前言 13 3 2 静态 KNN 的查询算法 14 3 3 动态 KNN 的查询算法 16 3 4 R 树的 KNN 查询算法 18 3 4 1 排序和剪枝过程 18 3 4 2 分支界限算法 19 3 5 本章小结 20 第 4 章 基于 R 树的障碍最近邻 ONN 查询 21 4 1 ONN 简介 21 4 2 相关工作 22 哈尔滨理工大学理学硕士学位论文 4 3 可视点的算法 23 4 3 1 基本概念 24 4 3 2 算法描述 24 4 3 3 时间复杂度分析 26 4 4 计算 qp 之间的最短障碍距离 ONN 26 4 4 1 寻找 qp 的障碍路径定义 26 4 4 2 根据 R 树来计算 qp 之间的障碍最近邻 27 4 5 本章小结 27 结论 29 参考文献 30 攻读学位期间发表的学术论文 34 致谢 35 哈尔滨理工大学理学硕士学位论文 1 第 1 章 绪论 1 1 研究的目的与意义 空间数据库 Spatial Databases 是数据库中最受关注的方向之一 也是实 际应用范围较广 查询效率较高的数据库之一 空间对象中无论是静止的还是 移动的 其运行轨迹都可以用空间数据库来存储和管理 而且对空间的各项数 据存储方面都较以往的数据库性能有较大的提高 因此 空间数据库的研究范 围非常广泛 涉及到空间对象和查询窗口等各个研究方面 空间数据库拥有巨大的数据存储量 也拥有极其复杂的空间结构 并且数 据类型随着空间位置的变换和查询窗口的变换而变换 因此空间数据库的查询 效率高低也就成了空间数据库性能的一个最重要的衡量标准 地理信息系统 GIS CAD CAM 等实际应用需求也对数据库的查询效率有更高的要求 因 此空间索引技术在数据库索引中是一个热点 空间数据库查询是空间数据库的基本操作 其中一种最重要的查询类型就 是最近邻 Nearest Neighbors NN 查询 最近邻查询是计算机查询领域中的 一个传统科学 这种查询类型通常应用于内容的相似性检索 模式识别 地理 信息系统 GIS CAD CAM 等 R 树是目前最常用的一种空间数据索引方法 并且广泛应用于空间数据库 及多维数据库中 它的结构与 B 树的结构相类似 在 B 树的基础上把查询窗 口变为最小包围矩形 MBR Minimum Bouding Rectangle 把空间的目标对象 看成是最小的包围矩形 MBR 用最小包围矩形来近似的表达空间对象 然 后通过空间范围查找来确定空间目标对象所在的地理位置 方便的对其进行索 引查找 R 树家族是目前公认的效率比较高的空间索引 最近邻查询问题 KNN 是 Knuth 在 1973 年提出来的 其可以简单描述 为 给定维空间内的个点所组成的集合 将这个点存储在一种数据结NnSn 构中 使得对于空间内的任何查询点 都能有效地找到它的最近邻 即在q 中找到一个点 使其到的距离最近 最近邻问题可以是一个 也可以是Spq 多个即 KNN 随着最近邻查询的发展 逐渐出现了反最近邻 Reverse Nearest Neighbor RNN 即给出一个数据集 然后从数据集中找出给定的约束区域 中找出查询点的 RNN 点 哈尔滨理工大学理学硕士学位论文 2 障碍最近邻 1 Obstructed Nearest Neighbor ONN 是指给定一个点和一个 障碍多边形的集合 寻找二个查询点之间的最短路径 ONN 查询在地理信息 系统和原始的空间数据分析中是一个广泛应用的独立工具 比如在聚类和分类 中存在的障碍问题 1 2 国内外研究现状分析 1 2 1 基于 R 树的空间索引现状 基于R 树的空间索引查询技术采用的是空间最小包围矩形MBR为查询对象 他把空间的查询对象近似的看做最小包围矩形 根据不同的MBR之间的相对关 系来建立相应的树形结构 当前对具有良好搜索性能的R 树的研究尤为活跃 对R 树的研究主要以两种研究思路展开 对R 树的优化改自1984年Guttman 2 提 出R 树以来 众多研究者针对不同的应用需求对R 树进行了各种改进 形成了 诸多R 树的变种 如文献 3 中介绍的优化oversize shelves R 树 文献 4 中新的 索引R link树 文献 5 中介绍了LUR 用来解决移动对象的查询问题 R 树 6 在 后面章节中要重点介绍 在查询效率上有很大的提高 SR树 7 Hilbert R tree 8 和SR tree把R 树查询效率有所提高或者提出了一个新的解决方案 文献 9 10 分 别介绍了移动的R树查询和多维数据空间的改进空间对象的R tree R 树 并介 绍了一些在应用领域的实例 文献 11 12 中介绍了基于窗口查询的HR tree和查 询执行成本模型的CUR Tree 文献 13 14 中介绍了用于实现空间连接的seeded tree 文献 15 16 17 分别提出了各自的改进R 树的方法 分别为OLAP范围查询R tree 并行的R 树 Master lient R trees和基于磁盘阵列的并行R 树等 1 2 2 最近邻查询现状 1 静态最近邻查询现状静态最近邻查询现状 静态最近邻查询的算法主要就有两种 一种是最佳优先遍历查询 BF 另一种是深度遍历查询 DF 首次提出深度遍历最近邻算法的是 Roussopoulos等人 18 其算法大致是对K D树查询算法的优化与改进 Kom等人 19 通过多次对终端数据的扫描 很巧妙的设计了一个多步骤的最 近邻查询算法 并获得了最终的查询结果 Berchtold等人 20 探讨了基于Vornoi图的最近邻查询算法 哈尔滨理工大学理学硕士学位论文 3 2 移动最近邻查询现状移动最近邻查询现状 Zheng和Lee 21 首先提出了基于Voronoi 的移动最近邻查询问题处理方法 Song和Roussopoulos 22 扩展了此算法 随后Tao和Papadias 23 提出了一种称之为 时间参数化的 TP 查询类型 Kollios等人 24 用对偶变换 dual transformation 解决了移动对象的移动最近 邻查询问题 Benetis等人 25 提出了基于最近邻查询方法和反最近邻查询方法来 求得移动对象的最近邻查询的解决方法 Iwerks等人 26 研究了基于K阶最近邻的联系移动对象的最近邻查询算 但 是此算法并没有从真正意义上提高查询的效率 Raptopoulou等人 27 从移动数据 库的角度解决了移动对象的移动最近邻查询问题 这个算法理论上有很大的应 用前景 移动对象最近邻的查询问题一直是最近数据查询的热点之一 在集中 环境下或者在分布环境下的最近邻查询问题又因为其在应用领域的广泛采用成 了最近研究的热点 28 Ferhatosmanoglu 29 研究了在查询受到外来数据干扰情况下的最近邻查询 Constrained Nearest Neighbor 问题 Papadias等人 30 首次探讨了组最近邻查 询 Group Nearest Neighbor 问题和聚类最近邻查询 Aggregate Nearest Neighbor 问题 Zhang等人 31 首次研究了空间对象的全最近邻查询 All Nearest Neighbor 问题和障碍最近邻查询 Obstructed Nearest Neighbor Query 问题 Deng等人 32 研究了表面最近邻查询 Surface k Nearest Neighbor Query 问 题 Hu和Lee 33 探讨了区域最近邻查询 Range Nearest Neighbor Query 问题 Nutanong 34 等人讨论了可视最紧邻查询 Visible k Nearest Neighbor Query 问 题 其目的是找到一个给定查询点的k个可视最近邻 近年来 我国国内的学者和专家也在最近邻查询算法方面取得了很大的成 就 拓展和建立了移动对象最近邻查询算法的许多分支算法 于忠诚 35 在研究 移动环境下查询点的的连续最近邻查询方面取得了丰硕的成果 卢炎生等人 36 改进的在静止状态下基于最佳优先遍历算法的最近邻查询算法 并把它推广到 移动对象的最近邻查询领域 刘云生等人 37 从聚类的角度出发 定义了一种新 的查询最近距离聚类查询的新算法 通过计算移动对象中一些点到中心对象的 距离之和 比较其距离和的大小来求得移动对象的K最近邻 廖巍 38 推广了K最近邻查询的算法 引入了可伸缩的增量算法 在查询的 效率上有一定的提高 但是过程比较复杂 距离实际应用还有一定的距离 哈尔滨理工大学理学硕士学位论文 4 1 3 课题来源 本课题属于应用基础研究范畴 来源于自拟算法研究 1 4 本文主要研究内容 1 研究空空间索引结构R 树索引的空间对象 2 在R 树的基础上 从减少树的叶节点出发 来缩小查找范围 以提高 算法的运行速度 3 基于R 树的K最近邻的查询算法 4 基于R 树的障碍最近邻 ONN 的查询算法 哈尔滨理工大学理学硕士学位论文 5 第 2 章 空间数据库索引 R 树 2 1 R 树的定义 R 树是 Guttman 于 1984 年提出来的一种动态平衡树 是把 B 树的思想扩 展到多维空间 对于一棵具有 M 阶的 R 树 其结点的结构可描述如下 叶结 点 中间结 2211 MM MBROIMBROIMBROILEVELCOUNT 点 其中 2211 MM MBRCPMBRCPMBRCPLEVELCOUNT 为数据存储项 代表目标的空间查询项 指的是维空 ii MBROI i OI i MBRk 间中查询目标的最小包围矩形 索引项为 指针指向是子树 ii MBRCP i CP 的根结点 代表其子树所包含的最小包围矩形 也就是包围其子树根结 i MBR 点中所有目录矩形最小包围矩形 简称目标矩形 表示结点中用MCOUNT 到的索引项或数据项个数 表示该 R 树中树的层数 由于数据和指0 LEVEL 针所占存储空间相同 且可以相互转换 因此 R 树是一棵高度平衡树 其叶子 结点的结构和中间结点的结构是类似的 如果为索引项的最小数目 通常取 和主要是用来 2 2 M mm m 2 M Mm 通过比较与结点所包含的项目数 的大小关系 来判断结点是上溢还是下溢 R 树必须满足如下特性 1 如果结点是叶结点 则结点至少要有两棵子树 否则结点就是根结点 2 中间结点的数量一定在与之间 除非这个结点是根结点 Mm 3 每个根节点要有两个或两个以上的叶结点 否则根结点也是叶结点 4 叶结点所包含的数据项或者指针项一定会在与之间 Mm 5 叶结点都应该在同一层上 6 结点的存储空间都是相同的 此外 R 树还具还有如下特性 1 存储的数据矩形是允许重叠的 2 查找的目标矩形也是可以重叠的 3 对精确查找来说 其大部分查找路径是多余的 哈尔滨理工大学理学硕士学位论文 6 由于 R 树的根结点和叶结点对应的空间区域可以重叠 而且存储数据矩形 也是允许重叠的 所以插入数据和删除数据就显的比较容易了 但也是因为最 小包围矩形可以重叠 特别是重叠的 MBR 还是查询目标所在的 MBR 时 对 查询点的索引可能导致从根结点到叶节点的遍历查询 其结果可能导致 R 树查 询性能的下降 如图 2 1 2 2 所示 图中的实线框表示空间目标的 MBR 821 rrr Minimum Bounding Rectangle 是指包含特定空间对象的最小矩形 它是空间 对象的一种近似表示 基于最小包围矩形 MBR 的空间索引均采用空间对象的 MBR 作为空间对象近似表示 然后根据 MBR 之间的空间关系建立相应的树形 结构 基于 MBR 的空间索引主要代表有 R tree 及其变种树 图中 表示空间点 点的 MBR 是其本身 虚线框表示中间 1021 ppp 821 RRR 结点索引项所对应的索引空间 即目录矩形 从图中我们可以看出 目录矩形 是可以重叠的 如 85 RR 1 r 5 r 6 r 2 r 3 r 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 4 r 7 r 8 r 9 r 1 p 4 p 5 p 2 p 3 p 6 p 7 p 8 p 9 p 10 p 11 p 图 2 1 R 树的平面示意图 Figure 2 1 R tree plane sketch 1 r 2 r 3 r 4 r 5 r 6 r 7 r 9 r 8 r1 p 2 p 3 p 4 p 5 p 6 p 7 p 8 p 9 p 10 p 11 p 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 图 2 2 R 树的结构示意图 Figure 2 2 R tree schematic 哈尔滨理工大学理学硕士学位论文 7 2 2 R 树的相关算法 2 2 1 R 树的查找算法 由于 R 树是 B 树的拓展 所以 R 树的查找方法也是对 B 树查找方法的改 进 都是从根结点开始向下查找 其查找算法是一个递归的过程 从根节点开 始查找 如果根结点同时不是叶结点的话 就依次沿着每条路径对每个叶结点 所对应的 MBR 和数据进行判断 如果查找区域与一个最小包围矩形相交 则 该最小包围矩形既是我们查找目标的所在包围矩形 如果不是所要查找的 MBR 遇到叶结点时查找的目标矩形必须在查找区域内进行遍历查找 查找区 域内的所有目标 依次判断各个空间对象与查找区域的关系 直至找到目标所 在的 MBR 如图 2 1 所示 查找空间目标中所有指定区域 图中粗虚线矩形区域 相P 交的目标 其过程为 1 查找各个 MBR 比较其是否与查找目标相交 图中从根结点开始查找 因为开始的两个根结点都与相交 则这两个根结点都有可能包含查找 21 R RP 的目标 因此 这两棵树我们都不能排除 只能依次查找 2 然后我们来从来开始查找 查找所包含的目标矩形 找到与相 1 R 1 RP 交的最小目标矩形 发现只有符合 对的子树进行比较 得到相应的目 5 R 5 R 标矩形 分别为标 则查找目标就有可能在 之中 我 7 r 7 p 7 p 7 r 7 p 7 p 们进一步比较其空间的坐标可得不一定是我们所查找的矩形 而则有可能 7 r 7 p 是我们所查找的目标矩形 3 同样用上面的方法来求得与相关的目标矩形 可以得到可能是要 2 R 8 r 查找的目标矩形 算法算法 2 1 查找算法查找算法 Algorithm R Search WN Begin If Then0 LEVELN Return rectangles that intersect with W Else For To Do1 iCHILDNUMN Begin 哈尔滨理工大学理学硕士学位论文 8 If Intersect with ThenMBRN W Search R WCPN End End 从上面的查找过程可以知道 如果想提高一棵 R 树的查找效率 我们就得 从以下几个方面进行改进 由 R 树的特点及其查找过程可知 要想得到一棵效率高的 R 树 须尽量 追求以下几点 1 从查找目标矩形的范围来看 应让其覆盖的区域尽可能的小 这样才 能保证查找的树的分支尽可能在更高的层次上进行 尽快的判断出目标所在的 包围矩形 来提高查找的效率 2 从查找目标矩形的 厚度 重叠的程度 来看 应该尽可能的减少重 叠区域对查找目标的影响 尽量使查找的目标矩形不重叠或者是少重叠 从而 来提高查找效率 3 从查找目标矩形的长度来看 目标矩形的周长尽量的小 也就是说应 该尽量让查找的目标矩形接近于正方形或者正方体 同过这样的调整来提高查 找的效率 4 从利用空间的角度来看 应该尽可能的增加空间的利用率 通过减少 树的层数和高度来提高查找的效率 2 2 2 R 树的插入算法 插入算法就是将新的索引项插入到树的叶节点的过程 插入的过程也是一 个递归的过程 首先从根结点出发 按照一定的插入要求 寻找插入索引项后 使最小包围矩形 面积 扩大最小的那个结点 遍历插入直至叶结点 然后从 叶结点出发 重复上面的操作步骤 把新的索引插入到叶结点中去 最后 对 新插入的索引项进行优化调整 当插入新索引项后使叶结点或者根结点上溢或 者下溢时 需要进行分裂操作 也就是将溢出的结点按照一定的规律分成几部 分 把原来的根结点删除 并加入新的分裂后的根结点 如果需要分裂的是根 结点 那么树的层数就是增加一层 算法算法 2 2 插入算法 插入算法 Algorithm R Insert PN Begin 哈尔滨理工大学理学硕士学位论文 9 If 0 LEVELN Begin Insert into PN If overfill Then Split NN End Else Begin R Insert PCPN i Adjust to enclose all rectangle i MBRN End End 需要注意的是 在进行插入算法的时候 叶结点和根结点的最小外包矩形 的面积可能会增加 这个变化直接导致从插入的索引项开始 向下的叶结点和 向上的根结点发生变化 导致根结点做出一定的调整 甚至可能导致根结点的 分裂 结点的分裂是一个相对复杂的过程 我们在下面介绍的就是结点分裂的 算法 关于结点的分裂算法 Guttman 分别提出过时间复杂度为 和的nlog 2 nn 分裂算法 其共同点都是使分裂时候产生的两个最小的目标矩形的范围尽量小 但比较后我们会发现 时间复杂度为的算法得到的解是比较优秀的 而时间 2 n 复杂度为和的算法得到的解相对效率较差 nlogn 下面以时间复杂度为也就是现行算法为例 来说明分裂算法的过程 我n 们用来表示空间的维数 表示分裂前的结点个数 第 项与第项之间的kNij 结点我们用来表示 可知 然后把分裂出来的结点 ij Nkj 111 Mi 分成两个组 分别为和 则分裂的过程为 1Group2Group 1 从的项中任取连个结点 使其满足N1 M s N t N 其中 jdidtbsb NNMAXNN 1 2 1 Mji 这样就能找到结点中距离比较远的两个结点 kd 2 1 kb 2 1 把这两个结点分别放入和中 1Group2Group 2 把中的所有包围矩形中面积最小的矩形用 则1Group j GroupMBR 可得 jijj MBRGroupNGroupMBRAreaE jj MBRGroupMBRAreaA 2 1 j 这时就需要对中剩余结点分别划分到或者中 具体处N i N1Group2Group 哈尔滨理工大学理学硕士学位论文 10 理过程如下 1 若和中已经含有项 就要把放到另外的一1Group2Group1 mM i N 组中 转下一步 2 若 那么 若 那么 转下 21 EE 1 GroupNi 21 EE 2 GroupNi 一步 3 若 那么 若 那么 则转 21 AA 1 GroupNi 21 AA 2 GroupNi 下一步 4 如果划分后所在的组的元素个数相等 则执行下一步 i N 5 可以放到任何一组内 i N 3 如果再增加另外的一个结点 这样和中分别存M1Group2Group 储了和 此时 如果的根结点上溢或者下溢 则同样也要进行分裂 NMN 2 2 3 R 树的删除算法 在 R 树的删除算法中 首先要找到需要删除的目标 也就是找到需要删除 的索引项所在的叶结点或者是根结点 删除该索引数据项后 如果删除目标对 应的数据项叶结点上溢 则依次向上调节根节点所对应的目标矩形 直至根结 点 而且要注意尽量插入到适当的层中 否则可能会因此树层数的增加 从而 影响查询效率 如果删除目标对应的数据项叶结点下溢 则用上述插入算法中 的过程 插入的结果可能导致树层数的增加 插入的最后要删除根节点的索引 项与相对应的叶结点的索引项 算法算法 2 3 删除算法 删除算法 Algorithm R Delete PN Begin If 0 LEVELN If contain ThenNP Begin Delete from PN 1 COUNTNCOUNTN Return True End Else Return False Else 哈尔滨理工大学理学硕士学位论文 11 For to Do1 iCOUNTN If intersects with Then i MBRN P If R Delete ThenTurePCPIN If ThenmCOUNTCPIN Adjust to enclose all child s rectangles i MBRN Else Begin ReInsert all remain entries of and delete CPIN CPIN If underfilled ReInsert all remain entries of it N and delete it too End End 2 2 4 R 树的算法总结 R 树的高效性使它超越了之前的很多空间数据索引结构 并随着人们研究 的深入 对 R 树的改进也日益完善 产生了很多基于 R 树的优化查询方法 这使得 R 树成为了当今最流行 最广泛 最成熟 运用率最高的空间数据索引 技术 2 3 R 树索引的优化 随着人们对查询效率的要求越来越高 R 树的一些缺点也明显的显露出来 R 树的缺点主要有以下两点 一是查询点可能沿着根结点的多条路径一直查询 到叶结点 特别是当查询点在重叠的区域时 这样可能会影响查询的效率 二 是由于目录矩形的空间有空白的区域 在查询的过程中 一些大的目录矩形的 重叠程度比较大 这就增加了树的高度和层数 随着目标矩形的增加 R 树的 查询性能也就随之下降 因此 改进重叠区域和缩小目录矩形是优化 R 树性能 的关键 因为 R 树的性能存在以上的一些缺点 所以许多学者和专家也一直在探索 改进和优化 R 树 对 R 树的优化大致分为两类 一类是整体优化 一类是局 部优化 整体优化是指从树的结构出发 考虑到整棵树的组织结构和数据结构 哈尔滨理工大学理学硕士学位论文 12 从而使树的性能有所改进 局部优化是指仅对树的某些局部结点和数据进行优 化 比如优化插入过程或者是优化分裂过程 很明显可以看出 如果仅仅考虑 局部优化而忽视整体优化的话 从局部来看可能树的性能会有所提高 但是这 样很难保证树的整体性能 而且一般情况下 结点的插入过程和分裂过程都是 局部优化的过程 所以要保证树整体性能的提高 就必须尽可能的把插入结点 或者分裂结点都进行优化 这样就会使优化的面积变大 从而使整体性能有了 一定的提高 局部优化主要指的是对插入过程中选择所要插入的叶结点的过程和插入后 结点的分裂过程 因此要保证 R 树的优化效果 必须选择合适的叶结点进行插 入 Guttman 也曾经给出了自己的改进 R 树的方法 但这个方法仅考虑一种特 殊情况 对一些特定标准的 R 树进行了讨论 而且并没有从整体上对 R 树进 行优化 也没有给出相应的优化算法 后来的许多专家 学者和研究人员在研 究 R 树的行能的时候 都考虑到了 R 树整体性能的优化 并取得的很显著的 成就 这就诞生了许多 R 树的变形树 1 R 树介绍的是查询点可以避免同时访问多条路径的一种树的结构 对查 询检索的性能有了一定的改善 2 R 树介绍的是使查询的目标矩形重叠尽可能小 从这个角度对 R 树进 行优化 3 Hilbert R 树是基于 R 树和 B 树的一种混合结构的树 该结构的基础是 Hilbert 空间的几何曲线来判断空间对象的位置关系 4 PR 树 The Priority R tree 是一种变化的渐进的最优 R 树 主要考虑 的是算法的 优先矩形 Priority Rectangles 2 4 本章小结 本章首先介绍了空间索引技术的 R 树的定义和 R 树的性质 并用图形演 示了 R 树的查找的过程 提出了 R 树的优缺点 然后介绍了 R 树的各类算法 知识 包括 R 树的查找算法 插入算法和删除算法 并介绍了算法的过程及算 法的伪代码 最后研究了 R 树的优化 包括整体优化和局部优化 分别分析了 它们的优缺点 并介绍了一些优化后的 R 树 包括 R 树 R 树 Hilbert R 树 PR 树 LR 树 本章也对 R 树索引的结构和算法进行了说明 为后面求最近邻问题作了铺 垫 哈尔滨理工大学理学硕士学位论文 13 第 3 章 基于 R 树的 K 最近邻查询 3 1 前言 最近邻查询 Nearest Neighbors Query NNQ 是计算几何和计算机科学中一 个很重要的领域 广泛的应用于模式识别 城市规划 地理信息系统 相似性 检索 路网建设 无线通信和全球定位系统等各个领域 地理信息系统 GIS 是实际生活中应用非常广泛 其在环境检测 电力 行业 空间气象 地质勘探 运输管理 已经在科技国防等各个领域都起着越 来越重要的作用 地理信息系统是来收集 分析 管理 查询与相关数据信息 的一种信息计算系统 并通过对数据的分析 可以为决策者提供一种科学分析 的平台 39 空间数据库的索引查询是地理信息系统的一个重要部分 空间数据的基本 功能就是数据查询 其中最近邻查询又是查询中一个最重要的部分 而地理信 息系统主要所采用的就是空间数据的最近邻查询问题 所以空间数据库的最近 邻查询研究就显得尤为重要了 最近邻问题可以描述为 给定多维空间中个点的集合和一个距离函数nS 最近邻问题就是为点集建立一个数据结构 当我们输入一个查询点时 DSq 我们能很快的找到与最近距离的点 其中 查询点的最近邻可q qsDsSs q 能是一个也可能是个 或者需要得到的是查询点的查询点个最近邻点 kqk 即 KNN 例如某船只在海上遇到事故 需要确定与其最近邻的五只渔船一起 去援助 这就需要在数据库中找到五个与它距离最近的渔船 在实际需要中 空间数据库的数据量特别巨大 数据结构也非常复杂 而且查询检索的时间和 空间代价也相当昂贵 因此空间数据库查询的效率就成了衡量数据库好坏的一 个重要标准 其中 最近邻查询问题也是空间数据查询中的重点和难点 随着移动通信 空间技术 数据技术的兴起 定位技术越来越成为许多国 家和企业争相发展的科技项目 美国的 GPS 已经广泛的应用到现实生活的各 个方面 欧洲的伽利略系统也逐渐的投入了使用 我国的北斗系统也对我们的 高速铁路 航空航天及航海提供了定位服务 而这些定位系统的基础就是移动 对象的位置数据查询 传统的空间数据库查询研究的主要方面就是欧氏空间 以目标距离为查询对象的 KNN RNN ONN 都是在欧氏空间 40 41 上来度量距 哈尔滨理工大学理学硕士学位论文 14 离 空间中的对象在定位服务中往往被约束在一些空间网格内 为了更加有效 地优化这些空间网格数据 人们就研究了用空间网络数据库来存储和查询这些 网格数据 每个传统的数据类型都在新的空间网格数据库中有所体现 如最近 邻查询 空间链接 范围查询 目标检索等等 对于在欧氏空间进行的 KNN 查询 通常都是以距离函数的计算相对容易 为基础 但是这个基础对于采用空间网格数据库来进行距离查询明显是不适用 的 因此需要在空间网格数据库中的最近邻查询问题进行更深入的研究来满足 让它能满足欧氏空间的距离函数 现在的许多关于近邻的数据结构和查询方法都是在欧氏空间下进行的研k 究 这样的窗口查询和范围查询并不是很好的处理 KNN 查询要求的好方法 因此 用 R 树这样一种常用的空间数据结构来进行 KNN 查询就显的十分重要 了 空间数据中的每一个数据单元都可以用 R 树的结点来表示 3 2 静态 KNN 的查询算法 静态 K 最近邻查询算法最早是由 Fredman 和 Tarjan 提出来的 采用的是 斐波纳契 Fibonacci 堆算法 其基础是 Dijkstra 算法的 主要是依靠网络的网 格距离排列来确定需要扩展的查询结点 结点在存储到数据库的时候需要分为 两层 一层是网络 另外一层是可能信息点 相对应的在斐波纳契 Fibonacci 堆中就产生了两种类型的项 结点项和可能信息点项 算法中结点项的扩展都 需要从这个结点关联的边返回 而可能信息点项的扩展只能在 B 树中进行简单 的来回往返移动 算法算法 3 1 KNN 算法查询算法查询 算法描述 KNN QA kq 输入输入 查询点 查询要求的最近邻数目 qk 输出输出 结果集 元素形式为 R pt cos 1 为已扩展过的节点和访问过的兴趣点的集合 R SSi0 2搜索网络边的 树 发现点所在的网络边Rqe 3在边的底层树中搜索点的相对位置 Bqpos 4打开一个向前的迭代器和一个向后的迭代器 检索和的下一个 w f w b f p b p 点 如果迭代器到达树的端部 这些点设为 B 5If then Insert f p 2 neNposleneheap 6 Else Insert ww fPposposfheap 哈尔滨理工大学理学硕士学位论文 15 7If then Insert b p 1 neNposheap 8 Else Insert ww bPposbposheap 9 While do kiheap 10 inf cosheapextractMinotypet inf oSS 11 If thenPtype 12 移动迭代器到下一个位置posopos inf pop inf oinf 13 If thenSpo inf 14 If then po inf 15 If 迭代器info 是向后的 thenoinf 16 Update cos 1 neNpostheap 17 Else 18 Update infcos 2 neNposlenotheap 19 Else If 迭代器是向后的 thenoinf 20 Update inf infcos oPposopostheap 21 Else 22 Update inf infcos oPposposopostheap 23 ptRR cos i 24 Else For each 节点的毗邻边 dooinfe 25 If then 打开向前的迭代器检索下一个点 1 infneo w f 26 If thenSpfw 27 If then pfw 28 Update cos 2 neNlenftheap w 29 Else 30 Update cos ww fPposftheap 31 Else 打开向后的迭代器检索下一个点 w b 32If thenSpbw 33 If then pbw 34 Update cos 1 neNlenbtheap w 35 Else 36 Update cos www bPposblenbtheap 37Return R 算法首先在网络树中搜索 发现包含点的边 第 2 行 然后在边的底 Rq 哈尔滨理工大学理学硕士学位论文 16 层树中搜索点的相对位置 第 3 行 接着树的两个迭代器分别向 Bqpos B 前和向后打开 将相应的点插入堆中 第 4 12 行 如果迭代器到达树的端 B 部 插入堆中一个节点 第 6 和 10 行 一个斐波纳契堆中需要包含以下信息 代表的是权值 代表的是tcostype 信息类型 代表的是信息的标号 其信息项会根据的值进行排序 inftcos 信息中包含了所有的信息 表示这个项的结点或可能信息点是项的类oinftype 型 对于结点和可能信息点来说 扩展的过程需要相应的迭代器 一般都采用 树的迭代器 迭代器中用表示方向 用表示存储的可能信 Bdir yx ppp 息点的坐标 用来代表边的长度 用来存储当前可能信息点的位置 lenpos 一个整体的树的迭代器用表示 B otypetinf cos 如果斐波纳契堆不是空集的话 并且时 从 Fibonacci 堆中取出一个ki 元素进行处理 如果取出的元素是可能信息点 就把它放入结果的集合中 R 如果不是可能信息点 就需要增加检索的距离并检查函数中变量的位置 如果 还在 Fibonacci 堆中 如果还在堆中而且插入的权值比较小 那么整个 Fibonacci 堆的权值就会变小 如果函数中变量的位置不在 Fibonacci 堆中 则 直接将变量插入到堆中 如果插入的原始是一个结点的话 就需要对这个结点进行扩展 从树 B 迭代器的两端开始检索每个与结点相邻的边 只需要检查迭代器的前后顺序e 和结点的始末点就可以找到下一个结点 如果下一个结点不属于 FibonacciS 堆的权值就会变大 也需要把相应的权值插入到堆中 3 3 动态 KNN 的查询算法 移动对象的数据是由若干个数据对象组成的 这些数据对象随着时间的改 变位置也发生了相应的改变 如城市的路网 移动电话用户等 在这种情况下 存储这些移动对象的数据库也要通过改变存储对象的 ID 坐标等数据来满足 新的查询需求 目标对象的动态 KNN 查询就是要求连续查询到移动目标的 个最近邻对象 下面介绍的方法是关于包含有结点和边的网络 其中的边是k 一个权值模型 表示通过一个点到下一个点所需要的时间 本方法能比较容易 的应用到边是单向移动的网络 当边的权值发生变换的时候 数据存储的服务 器就会改变相对应的信息 查询目标之间的距离就被