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

基于预计算的路网k路径近邻查询研究

作　者: 韩静静
导　师: 王宝文
学　校: 燕山大学
专　业: 计算机应用技术
关键词: 预计算 NN lists Voronoi图 k路径近邻移动对象数据库
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 23次
引　用: 0次
阅　读: 论文下载

内容摘要

随着卫星全球定位系统和无线通讯技术等科学技术的快速发展,已经能够跟踪并记录移动对象的位置信息。移动对象在地理信息系统、移动计算和基于位置的电子商务等方面发挥着重要应用,各种查询方法不断提出。k路径近邻查询(k-PNN)作为一种新的查询方法,对用户的实时查询要准确快速的给出回答,因此,降低查询代价成为该查询方法的关键问题。Zaiben Chen等人提出了最优路网扩展(BNE)方法。本文中,运用预计算思想减少路网扩展代价,旨在进一步提高查询效率。首先,运用预计算思想提出了基于NN lists的BNNL算法,运用双向Dijkstra算法向在获得用户当前位置和目的地节点之间最短路径的基础上,预计算路网节点的m近邻信息,运用优先队列进行优化处理。对于路口节点的近邻不需要路网扩展得到,只需进行简单读取,从而提高了BNNL算法对路网k路径近邻的查询效率。其次,Voronoi图不仅对路网进行了简化处理,还预计算了路网中部分节点之间的最短距离,减少节点扩展次数,从而提高近邻查找效率。本文提出的基于Voronoi图的路网k路径近邻查询方法(VBk-PNN)。将相同的路网Voronoi多边形在用户当前位置和目的地节点之间最短路径上的路口节点作为一个集合来进行扩展。并运用优先队列进行优化处理,最终得到正确的k路径近邻。最后,通过实验将上述提出的两种方法和已有的最优路网扩展方法(BNE)进行实验比较,结果表明BNNL算法和VBk-PNN算法的执行效率均优于BNE算法。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-18
  1.1 研究背景及意义  10-11
  1.2 国内外研究现状  11-15
    1.2.1 k 近邻查询研究现状  11-14
    1.2.2 路径近邻研究现状  14-15
  1.3 研究内容  15-16
  1.4 本文的结构安排  16-18
第2章基础知识概述  18-26
  2.1 移动对象  18-20
    2.1.1 概念  18
    2.1.2 分类  18-19
    2.1.3 特点  19-20
  2.2 典型预计算方法介绍  20-25
    2.2.1 NN lists 的基础知识  20-21
    2.2.2 Voronoi 图的基础知识  21-24
    2.2.3 其它预计算方法  24-25
  2.3 本章小结  25-26
第3章基于NN lists 的路网k 路径近邻查询  26-40
  3.1 引言  26-27
  3.2 相关工作  27-29
  3.3 问题定义  29-30
  3.4 BNNL 算法  30-37
    3.4.1 UNICONS 算法在近邻问题中的应用  31-32
    3.4.2 BNNL 算法思想  32-33
    3.4.3 数据结构  33
    3.4.4 BNNL 算法描述与分析  33-37
  3.5 实例分析  37-39
  3.6 本章小结  39-40
第4章基于Voronoi 图的路网k 路径近邻查询  40-54
  4.1 引言  40
  4.2 Voronoi 图在近邻问题中的应用  40-43
  4.3 VBk-PNN 算法  43-51
    4.3.1 VN3 方法  44-48
    4.3.2 算法思想  48
    4.3.3 数据结构  48
    4.3.4 算法描述与分析  48-51
  4.4 实例分析  51-53
  4.5 本章小结  53-54
第5章模拟实验与性能分析  54-62
  5.1 实验环境设置  54-55
  5.3 近邻查询实验结果及分析  55-57
  5.4 k 路径近邻查询实验结果与分析  57-61
  5.5 本章小结  61-62
结论  62-64
参考文献  64-69
攻读硕士学位期间承担的科研任务与主要成果  69-70
致谢  70-71
作者简介  71

基于预计算的路网k路径近邻查询研究

内容摘要

全文目录

相似论文