移动对象反向k近邻查询研究

论文摘要

近年来,移动设备和无线网络的广泛应用带来了基于位置的服务（LBS）应用的快速发展。位置信息相关的查询在LBS中扮演了极为重要的角色。其中一种重要的查询是（单色）反向k近邻查询（RkNN）,该查询能够返回所有以查询点作为k近邻的对象集合。随着无线通讯技术的发展,用户已不再满足于仅获取静止对象的信息,还希望LBS应用能够提供移动对象的信息。当前,针对移动对象的空间查询受到了越来越多的关注。给定一个查询点q和一个查询时间段T,移动对象反向k近邻查询（M-RkNN）能够返回T时间段内所有时刻查询点q的反向k近邻集合。现有唯一能够处理该查询的算法（M-SAA）存在效率不高和只能处理2维移动对象等缺陷。为解决这一问题,本文提出了一种能够有效解决多维M-RkNN查询的新算法（M-TPL）。该算法基于过滤-精炼框架,并整合了两种高效的动态裁剪策略：移动对象支配域和时变最小包围盒对角线长度裁剪策略。当查询点也是线性运动时,M-RkNN问题将变得更加复杂。给定一个查询点q和一个查询时间段T,其中q使用关于t的线性函数表示,移动对象连续k近邻查询（CM-RkNN）可以返回查询时间段T内任意时刻查询点q在新位置的反向k近邻集合。本文首次提出并正式定义了CM-RkNN查询,并且给出了能够高效处理该查询的CM-TPL算法。实验结果表明：（1）M-TPL算法在2维数据集上比M-SAA算法大幅节省I/O和查询时间开销,并且它能够有效处理多维M-RkNN查询,且查询性能并不随维度增长下降；（2）CM-TPL算法能够高效处理多维CM-RkNN查询。

论文目录

• 摘要
• Abstract
• 图目录
• 表目录
• 第1章 绪论
• 1.1 课题背景
• 1.2 研究现状
• 1.2.1 空间数据库与空间索引技术
• 1.2.2 静态对象k近邻和反向k近邻查询
• 1.2.3 移动对象k近邻和反向k近邻查询
• 1.3 移动对象反向k近邻查询存在的问题和难点
• 1.4 本文的工作和组织结构
• 第2章 移动对象反向k近邻查询框架
• 2.1 查询框架和模块划分
• 2.1.1 移动对象索引模块
• 2.1.2 动态裁剪模块
• 2.1.3 查询处理模块
• 2.1.4 查询用户界面
• 2.2 本章小结
• 第3章 多维移动对象反向k近邻查询
• 3.1 多维移动对象反向最近邻查询
• 3.1.1 查询定义
• 3.1.2 移动对象支配域裁剪策略
• 3.1.3 时变最小包围盒对角线长度裁剪策略
• 3.1.4 多维移动对象反向最近邻算法
• 3.2 多维移动对象反向k近邻查询
• 3.2.1 查询定义
• 3.2.2 反向k近邻扩展裁剪策略
• 3.2.3 多维移动对象反向k近邻算法
• 3.3 本章小结
• 第4章 多维移动对象连续反向k近邻查询
• 4.1 查询定义
• 4.2 连续反向k近邻扩展裁剪策略
• 4.3 多维移动对象连续反向k近邻查询算法
• 4.4 本章小结
• 第5章 实验和分析
• 5.1 实验环境和设置
• 5.2 实验评价指标
• 5.3 二维移动对象反向k近邻查询对比实验及分析
• 5.3.1 k值影响
• 5.3.2 查询时间段长度影响
• 5.3.3 数据集大小影响
• 5.4 多维移动对象反向k近邻查询实验及分析
• 5.4.1 k值影响
• 5.4.2 查询时间段长度影响
• 5.4.3 数据集大小影响
• 5.5 多维移动对象连续反向k近邻查询实验及分析
• 5.5.1 k值影响
• 5.5.2 查询时间段长度影响
• 5.5.3 数据集大小影响
• 5.6 本章小结
• 第6章 总结和展望
• 6.1 本文主要工作和贡献
• 6.2 未来研究方向
• 参考文献
• 攻读硕士学位期间主要的研究成果
• 致谢