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

聚集最近邻查询技术研究

作　者: 张小菲
导　师: 徐建
学　校: 杭州电子科技大学
专　业: 计算机应用技术
关键词: 空间查询 聚集最近邻查询 Voronoi图 影响区域
分类号: TP311.13
类　型: 硕士论文
年　份: 2014年
下　载: 1次
引　用: 0次
阅　读: 论文下载
 

内容摘要


随着移动设备的不断普及，基于空间位置的查询服务已经逐渐渗入到人们生活的方方面面。无论是从欧式空间的查询研究到路网环境下的查询研究，还是从静态对象的查询研究到移动对象的查询研究，空间数据库查询已变得越来越多样化和复杂化。聚集最近邻(Aggregate Neareast Neighbor, ANN)查询作为一种基于位置服务的空间查询技术，已经成为当前的一个研究热点问题。ANN查询检索的是到多个查询点距离的聚集函数值最小的目标对象，其查询结果依赖于确定的聚集函数。目前，ANN查询已经存在不少的研究成果，主要包括欧式空间和路网环境两个方面的研究，然而现有的路网环境下ANN查询算法存在空间检索范围大以及距离计算冗余多的问题。针对这些不足，本文首先提出了一种基于影响区域的ANN查询算法。考虑到大量查询位置同时发起查询请求且要求查询结果能够及时反馈的实际需求，本文接下来提出了一种基于影响区域的快速ANN查询算法。首先，分析了ANN查询本身的一些特性，并总结了网络Voronoi图在网络空间中计算距离的优势，引入了影响区域的基本概念，并且给出了相应的构建算法。接着，通过对基于Voronoi图的ANN查询算法的深入分析，本文给出了一种基于影响区域的ANN查询算法。该算法将Voronoi图和影响区域相结合，在缩小查询空间范围的同时也大大减少了距离的计算。而后，用真实的数据集分别对sum聚集函数和max聚集函数做了对比实验。实验验证了基于影响区域的ANN查询算法比基于Voronoi图的ANN查询算法具有更高的效率。最后，针对大量查询点数据的处理需求，引入了查询分组和查询代表点相关概念，并给出了一种基于影响区域的快速ANN查询算法。该算法是以牺牲查询结果的准确率来达到提高查询速度的目的。实验给出了查询分组和组内包含的查询点个数对该算法性能的影响。本文针对现有ANN查询算法中存在的不足，创新地提出了基于影响区域的ANN查询算法，从而能够获得较高的查询效率。另外，又以现实需求为驱动，给出了基于影响区域的快速ANN查询算法。总之，本文提出的ANN查询算法是对现有查询算法的改进。

全文目录


摘要  5-6
ABSTRACT  6-10
第1章 绪论  10-14
  1.1 研究背景和意义  10-11
  1.2 国内外研究现状  11-12
  1.3 研究的主要内容  12-13
  1.4 文章组织结构  13-14
第2章 聚集最近邻查询相关技术概述  14-28
  2.1 空间数据索引技术  14-17
    2.1.1 基于四叉树的空间索引  14-15
    2.1.2 基于 R 树的空间索引  15-16
    2.1.3 基于网格的空间索引  16-17
  2.2 最近邻查询技术概述  17-23
    2.2.1 传统最近邻查询技术  18-19
    2.2.2 网络最近邻查询技术  19-21
    2.2.3 连续最近邻查询技术  21-23
  2.3 聚集最近邻查询技术概述  23-27
    2.3.1 欧式空间的聚集最近邻查询技术  24-25
    2.3.2 路网环境的聚集最近邻查询技术  25-27
  2.4 本章小结  27-28
第3章 聚集最近邻查询的预处理  28-34
  3.1 路网数据模型  28-29
  3.2 NVD 的基本概念  29-30
  3.3 NVD 的构造方法  30-32
  3.4 NVD 的存储方式  32
  3.5 本章小结  32-34
第4章 一种基于影响区域的 ANN 查询算法  34-46
  4.1 引言  34
  4.2 系统模型  34-35
  4.3 CVANN 查询算法  35-39
    4.3.1 影响区域的构建算法  35-37
    4.3.2 聚集函数的查询算法  37-38
    4.3.3 实例分析  38-39
    4.3.4 性能分析  39
  4.4 实验评估  39-44
    4.4.1 实验环境  39-40
    4.4.2 查询点规模对算法的影响  40-42
    4.4.3 目标对象规模对算法的影响  42-44
  4.5 本章小结  44-46
第5章 一种基于影响区域的快速 ANN 查询算法  46-54
  5.1 引言  46
  5.2 系统模型  46-47
  5.3 QCVANN 查询算法  47-50
    5.3.1 查询点分组的构建算法  47-49
    5.3.2 实例分析  49-50
    5.3.3 性能分析  50
  5.4 实验评估  50-52
    5.4.1 实验环境  50
    5.4.2 分组个数对算法的影响  50-51
    5.4.3 组内查询点个数对算法的影响  51-52
  5.5 本章小结  52-54
第6章 总结与展望  54-56
  6.1 本文工作总结  54-55
  6.2 今后工作展望  55-56
致谢  56-57
参考文献  57-63
附录  63-64
  发表的学术论文  63
  参加的科研项目  63-64
详细摘要  64-66

相似论文

  1. 基于密度的局部离群点挖掘算法研究,TP311.13
  2. 基于模型预测控制的足球机器人轨迹跟踪控制研究,TP242.62
  3. 基于颜色支撑点集、Voronoi图和Fréchet距离的几何算法研究,TP301.6
  4. 基于WebGIS的辽河油田土地信息管理系统的研究与实现,TP311.52
  5. 基于地理本体的地理信息语义表达与查询方法研究,P208
  6. 基于GIS的供热信息处理关键技术的研究,P208
  7. 距离邻近与自然邻近典型聚类方法比较,P208
  8. 障碍Voronoi图性质及其应用研究,O18
  9. 地下水曝气法的模型试验研究,X523
  10. 空间复杂区域间拓扑关系研究,P208
  11. 三角剖分的应用研究,TP391.72
  12. 不确定方向关系查询的研究,TP311.13
  13. 加权Voronoi图矢量生成算法研究及其实现,P208
  14. 基于Voronoi图的数字电视地面广播台站选址分析,TN949.197
  15. 动态大地测量数据融合有关问题研究,P22
  16. 面向航迹规划的电子沙盘技术研究,P208
  17. 基于GIS的山东半岛城市群空间布局研究,P208
  18. 基于Delaunay三角剖分的TSP问题求解研究,O224
  19. 基于样点拓扑邻域的散乱点云曲面重建,TP391.72
  20. 基于地震监测台网资料的震动图及震动烈度研究,P315
  21. 基于高效空间存取机制的地理空间数据查询研究,P208

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com