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

路网中基于Voronoi图的聚集最近邻查询技术研究

作　者: 朱良
导　师: 孙未未
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 道路网络路网Voronoi图聚集最近邻查询
分类号: TP311.13
类　型: 硕士论文
年　份: 2012年
下　载: 61次
引　用: 0次
阅　读: 论文下载

内容摘要

移动计算、无线通信以及定位技术的快速发展使得对各种空间对象的存储和管理成为了现实需求。大量的应用领域(如地理信息系统、道路辅助与导航、急救服务、交通管制、与生活服务相关的查询、军事、移动电子商务等)均迫切需要有效地查询这些数据对象。然而,空间数据固有的海量性和复杂性使得传统的数据库查询处理技术不能或不能有效地发挥作用,需要研究新的查询处理技术。因此,如何提供各种高效的空间对象查询处理技术是当前空间数据库领域的研究热点之一。空间数据库查询技术大都是基于欧式空间环境和道路网络(路网)环境。相比较而言,路网环境下的空间数据库查询会更有意义。因为它把空间对象限制在道路上,且查询点和空间对象只能按照路径移动。在路网环境下的查询与我们的生活更贴切。例如某个人找离他最近的加油站或餐馆。查询效率是空间数据库性能的重要指标,尽管有许多学者研究了路网中的空间数据库查询,并取得了许多成果,但距离满足用户不断出现地、复杂而多样的查询需求还是有一定的差距,仍需要进一步深入研究。本文主要研究了路网环境下的聚集最近邻(Aggregate Nearest Neighbor,ANN)查询。当前对路网环境下ANN查询的研究有两个缺陷：1.文献[1]性能最好的算法只适用于路网中边的权值与其长度成比例的情况。2.在有大量查询点的ANN查询中,算法的查询性能会很差。鉴于此,本文在路网Voronoi图(Network Voronoi Diagram, NVD)的基础上,提出高效的算法解决ANN查询。本文提出的算法不仅解决了上述两个缺陷,而且在绝大部分情况下,算法性能要优于文献[1]中的算法。论文的主要贡献如下：1.本文使用NVD解决路网中的ANN查询,据我们所知,这是第一篇基于NVD解决ANN查询的文章；2.针对sum聚集函数和max聚集函数,分别设计了高效的剪枝策略；3.提出了VANN算法解决ANN查询、证明了算法的正确性、分析了时间复杂度。4.提出了AANN算法来解决大量查询点的ANN查询。5.提出了k-VANN算法解决k-ANN查询,可以增量式地获取下一个ANN。6.本文采用真实数据集做了详细的实验,实验表明,本文提出的VANN算法和k-VANN算法的性能在绝大部分下要优于文献[1]中的算法。

全文目录

摘要  3-4
Abstract  4-9
第1章引言  9-14
  1.1. 研究背景  9-10
  1.2. 研究意义  10-11
  1.3. 研究内容  11-12
  1.4. 本文工作  12
  1.5. 文章结构  12-14
第2章相关工作  14-25
  2.1. 空间索引技术  14-17
    2.1.1. 基于R树的空间索引  14-16
    2.1.2. 基于四叉树的空间索引  16
    2.1.3. 基于网格的空间索引  16-17
  2.2. NN查询及其变体  17-23
    2.2.1. 基于欧式空间的查询  18-20
    2.2.2. 基于路网环境的查询  20-23
    2.2.3. 移动对象的NN查询及其变体  23
  2.3. 其他种类的查询  23-24
  2.4. 本章小结  24-25
第3章背景知识  25-34
  3.1. Voronoi图  25-26
  3.2. NVD定义  26-27
  3.3. NVD生成方法  27-28
  3.4. NVD的存储模式  28-29
  3.5. 基于NVD的k-NN查询  29-32
    3.5.1. 过滤步骤  29-30
    3.5.2. 精确步骤  30-32
  3.6. ANN查询  32-33
  3.7. 本章小结  33-34
第4章基于NVD的ANN查询处理方法  34-57
  4.1. 查找阶段  35-37
  4.2. 剪枝阶段  37-42
    4.2.1. sum聚集函数的剪枝策略  37-39
    4.2.2. max聚集函数的剪枝策略  39-42
  4.3. 基于NVD的ANN算法  42
  4.4. 分析  42-44
    4.4.1. 查询点扩展顺序  42-43
    4.4.2. 算法优化  43-44
    4.4.3. 正确性证明  44
    4.4.4. 时间复杂度分析  44
  4.5. 近似ANN查询算法  44-47
    4.5.1. 查询点划分方法  45-47
    4.5.2. AANN算法  47
  4.6. 实验评估  47-56
    4.6.1. 实验环境  47-48
    4.6.2. 实验结果与讨论  48-56
  4.7. 本章小结  56-57
第5章基于NVD的k-ANN查询处理方法  57-65
  5.1. 基于NVD的k-ANN算法  57-59
  5.2. 实验评估  59-64
    5.2.1. 实验环境  60
    5.2.2. 实验结果与讨论  60-64
  5.3. 本章小结  64-65
第6章总结和展望  65-67
  6.1. 本文总结  65
  6.2. 将来工作  65-67
参考文献  67-73
致谢  73-74
攻读硕士学位期间的研究成果  74-75

路网中基于Voronoi图的聚集最近邻查询技术研究

内容摘要

全文目录

相似论文