学位论文 > 优秀研究生学位论文题录展示

空间数据库中基于R-树的最近邻查询方法研究

作　者: 李若愚
导　师: 张健沛
学　校: 哈尔滨工程大学
专　业: 计算机应用技术
关键词: 空间数据库空间索引近邻查询等距离线剪枝
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 77次
引　用: 0次
阅　读: 论文下载

内容摘要

空间数据固有的海量性和复杂性使得传统的数据库查询处理技术不能或不能有效地发挥作用,需要研究新的查询处理技术。因此如何提供各种高效的空间索引与空间对象查询处理技术是当前空间数据库领域的研究热点之一。至今人们提出了利用多种不同类型的空间索引结构对空间数据库进行查询,其中大多数都是基于R-树索引结构的,例如最近邻查询、反最近邻查询、连续最近邻查询以及最近对查询等。目前现有的最近邻查询方法多是集中在目标对象为实际对象而把查询对象简化为一个空间点的情况下进行研究的,而在实际应用中,查询对象在很多情况下也同样是空间中的一个实际对象,所以把查询目标简化为一个空间点的方法存在着极大的局限性。在查询算法的实际执行过程中,由于选取的剪枝策略不能适应实际情况,常常需要访问许多实际上并不包含最近邻的MBR,从而增加了空间数据库中读入对象的I/O耗费,以及计算两个实际空间对象之间的距离耗费,增加了计算量,造成了算法的效率低下。针对目前最近邻算法所存在的不足,本文主要在以下几方面做出改进。首先,为了更加符合实际查询的需要,本文将查询对象的模型由一个空间点扩展为空间中具体对象的二维边界,并针对两个具体空间对象的距离,给出了其距离估计的上界和下界。其次,将等高线的思想引入到近邻查询中,提出了等距离线的概念,从而为两个具体空间对象之间距离的下界提供了一个更为精确的估计。再次,在等距离线的基础上,提出了一种剪枝策略,并给出了具体的最近邻查询处理算法。最后,通过实验验证了算法的正确性和有效性。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-16
  1.1 课题研究的背景和意义  10-11
  1.2 国内外研究现状  11-15
    1.2.1 静态对象的最近邻查询  11-13
    1.2.2 移动对象的最近邻查询  13-15
  1.3 论文的主要研究内容及结构  15-16
第2章空间数据索引技术及近邻查询方法概述  16-35
  2.1 空间数据及其表示  16-17
  2.2 空间索引技术及其分类  17-20
  2.3 典型的空间索引R-树  20-28
    2.3.1 查找算法  22-23
    2.3.2 插入算法  23-24
    2.3.3 删除算法  24-25
    2.3.4 分裂算法  25-28
  2.4 空间K 近邻查询方法研究  28-34
    2.4.1 BAB 算法  28-29
    2.4.2 BF 算法  29-32
    2.4.3 移动对象的静态近邻查询算法  32-34
  2.5 本章小结  34-35
第3章基于等距离线的空间K 近邻查询方法  35-50
  3.1 问题的提出  35-36
  3.2 相关概念  36-42
    3.2.1 距离定义  36-41
    3.2.2 等距离线  41-42
  3.3 基于等距离线的KNN 算法  42-49
    3.3.1 K 近邻搜索剪枝规则  43-45
    3.3.2 算例  45-49
  3.4 本章小结  49-50
第4章仿真与分析  50-55
  4.1 实验环境  50
  4.2 算法思想  50-51
  4.3 结果分析  51-54
  4.4 本章小结  54-55
结论  55-56
参考文献  56-62
攻读硕士学位期间发表的论文和取得的科研成果  62-63
致谢  63

空间数据库中基于R-树的最近邻查询方法研究

内容摘要

全文目录

相似论文