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

移动对象轨迹的最近邻居查询研究

作　者: 李春
导　师: 陈根才
学　校: 浙江大学
专　业: 计算机科学
关键词: 移动对象轨迹 TB树 k最近邻居查询受限k最近邻居查询
分类号: TP311.13
类　型: 硕士论文
年　份: 2007年
下　载: 207次
引　用: 4次
阅　读: 论文下载

内容摘要

随着无线通讯和位置定位系统的发展，移动对象数据库(MOD)变得越来越重要，也对数据库研究提出了极大的挑战。基于时间和空间的查询算法成为一些基于位置的服务急需解决的问题。比如：交通控制，近邻信息访问和对野生动物迁徙特性的分析等。而其中一个重要的查询类型就是k最近邻居(kNN)查询。它主要用来查询离某一移动对象最近的k个轨迹。据我们所知，在已有的研究文献中，研究学者们主要处理的是对于一系列连续移动点的将来或者当前位置的查询，这些查询或者基于静态的查询点或者基于连续移动的查询点。但是对于历史移动对象轨迹的最近邻居查询却很少。基于此，在本文中，首先，我们提出了两种基于最佳优先(Best-First)策略的算法：BFPkNN和BFTkNN。分别刚来处理静态查询点以及移动轨迹的k最近邻居(kNN)。并且为了减少内存消耗和CPU时间，本文给出了一些有效的剪枝策略。这些剪枝策略能够有效的避免访问那些不可能包含最终结果的节点，也能剔除掉那些不会成为最终结果的迹线段。其次，我们还提出了存历史移动对象轨迹上处理连续k最近邻居查询的两个算法：HC_p-kNN和HC_T-kNN。同时我们分析并给出了在连续kNN查询中常用的维护和和新k个最近邻居列表(kNearestLists)算法。再次，本文提出了在存储有历史移动对象轨迹的基于R树的索引结构上进行受限k最近邻居(CkNN)查询的概念，以及有效的处理方法。具体来说，为了有效处理CkNN我们提出了区域查询和kNN查询的依次查询方法以及在kNN查询中整合区域查询的方法。另外，我们还给出了两个算法，一个是截取迹线段得到时间域在某一范围内，空间区域包含在受限区域C内的部分迹线段的算法，另外一个是截取节点获得时间在指定范范围，空间范围在CR内的部分记录的算法。

全文目录

摘要  3-4
Abstract  4-11
第一章绪论  11-23
  1.1 研究背景  11-18
    1.1.1 数据库索引  11-13
    1.1.2 移动对象和移动对象数据库  13-15
    1.1.3 基于 R-tree的移动对象索引技术  15-18
  1.2 研究内容  18-20
  1.3 研究目标  20
  1.4 本文结构组织  20-21
  1.5 本章小结  21-23
第二章历史移动对象的查询研究综述  23-28
  2.1 区域查询  23-24
  2.2 基于轨迹查询  24
  2.3 k(≥1)最近邻居查询  24-25
  2.4 相似轨迹查询  25-26
  2.5 不确定轨迹查询  26
  2.6 本章小结  26-28
第三章历史移动对象的k最近邻居查询  28-44
  3.1 引言  28
  3.2 相关工作  28-29
  3.3 度量(metric)  29-33
    3.3.1 TB树  29-30
    3.3.2 剪枝策略  30-33
  3.4 点的k最近邻居查询算法  33-35
    3.4.1 算法描述  33-34
    3.4.2 算法分析  34-35
  3.5 轨迹的k最近邻居查询算法  35-38
  3.6 实验评估  38-43
    3.6.1 BFPkNN算法的实验结果  39-41
    3.6.2 BFTkNN算法的实验结果  41-43
  3.7 本章小结  43-44
第四章历史移动对象的连续k最近邻居查询  44-59
  4.1 引言  44-45
  4.2 相关工作  45-46
  4.3 k最近列表的更新  46-51
  4.4 点的连续k最近邻居查询算法  51-53
  4.5 轨迹的连续k最近邻居查询算法  53-54
  4.6 实验评估  54-57
    4.6.1 HC_PkNN算法的试验结果  55-56
    4.6.2 HC_TkNN算法的试验结果  56-57
  4.7 本章小结  57-59
第五章历史移动对象的受限k最近邻居查询  59-77
  5.1 引言  59-60
  5.2 相关工作  60-61
  5.3 历史移动对象轨迹上的受限kNN查询定义  61-63
  5.4 静止点受限k最近邻居查询算法  63-69
    5 4.1 “两步走”策略  63-65
    5.4.2 “一步走”策略  65-69
  5.5 轨迹受限k最近邻居查询算法  69-72
  5.6 实验评估  72-76
    5.6.1 CkNN_P算法的试验结果  73-75
    5.6.2 CkNN_T算法的试验结果  75-76
  5.7 本章小结  76-77
第六章总结与展望  77-80
  6.1 本文完成的主要研究工作  77
  6.2 本文的主要贡献以及创新点  77-78
  6.3 进一步的研究工作  78-80
参考文献  80-87
攻读硕士学位期间主要的研究成果  87-88
致谢  88

移动对象轨迹的最近邻居查询研究

内容摘要

全文目录

相似论文