路网中移动对象最近邻及反向最近邻查询处理研究

摘要

无线广播技术高速发展和移动通信设备的不断普及使得位置相关服务(location-based services，LBSs)越来越走进我们的日常生活。而位置相关查询处理(location-based queries，LBQs)作为位置相关服务的支持性技术之一，已经成为一个研究热点问题。近年来，研究者们对位置相关查询，特别是最近邻查询和反向最近邻查询进行了深入的研究，提出了许多有效的查询处理方法。但是，在最近邻查询方面，目前尚无人提出路网中可变速移动对象的连续k近邻查询处理算法；在反向最近邻方面，目前尚无人提出彻底的、对象和查询点均可连续移动的、路网中连续反向k近邻处理算法。目前位置相关查询处理的主要形式都是基于传统的按需访问（on-demand access）模式。按需访问方式只适合于无线信道和服务器处理容量都充足的轻负载系统。当客户量大、客户发起的移动查询量大时，服务器的处理能力和无线信道的带宽都会影响到查询处理的效率和速度。近年来，人们开始关注数据广播环境下的位置查询处理的研究，也提出了一些研究成果。但是到目前为止，这些研究只是局限于欧氏空间。欧氏空间环境下的相关算法是不能通过简单的修改而应用到路网环境下的，所以研究数据广播环境下路网中位置查询处理算法是非常迫切、必要的。
　　首次讨论了路网中反向k近邻查询连续监控问题(CRkNN)，分析了路网中移动对象连续反向k近邻查询的关键技术。提出了一种全新的称为DLM树的数据结构来索引CRkNN查询的监控范围，从而将CRkNN查询问题的处理简化为监控几个多路树，而不必在位置更新发生时重新计算查询结果。提出了统一解决单色数据集和双色数据集上反向k(≥1)近邻查询的框架和相应算法；为进一步提高算法的效率，给出了有关引理以尽可能地削减查询空间，并提出一些优化技术以高效地处理与查询结果有关的位置更新。模拟实验表明所提出的算法是有效的。
　　讨论了路网中不定速移动对象连续k近邻查询(CUkNN)的处理问题，分析目前现有的路网中移动对象连续k近邻查询算法的局限性。提出了一种不确定路网距离计算模式以计算路网中不定速移动对象和移动查询点之间的距离。基于这种距离模式，提出了两种CUkNN的连续监控算法，即CUkNN PLS和CUkNN Mean。在CUkNN PLS算法中，引入了可能距离区域和可能距离线段(PLS)的概念，以简化对象o成为查询q的kNN之一的概率值的计算。在CUkNN Mean算法中，为了进一步简化概率的处理，我们没有计算每个候选对象的成为查询q的kNN之一、确切的概率值，而是提出了一种有效的方法来将所有可能成为查询q的kNN结果之一的对象按照其概率值递减的顺序进行排列，选择排在前k位的对象构成最终的kNN结果集。此外，提出了一种处理对象速度超出界限和对象移动方向发生改变的方法，以维持查询结果持续有效。通过用一种新颖、规整的方法组织有关数据结构，扩展所提出的CUkNN算法以高效地、低磁盘访问代价地处理大路网中的CUkNN查询。模拟实验验证了所提出算法的有效性和可扩展性。
　　首次讨论了无线广播环境下路网中连续最近邻查询处理问题(CNBNN)。通过用属性obj_dom来标记路网上每一条边，以表明该边属于某个特定对象的voronoi多边形，提出了NVD结构以保留NVD图的特性。提出了一种称之为NVD四分划分的路网划分方法，将路网划分为一系列网格单元。特别地，各网格单元占据大致相同的存储空间，而且具有较好的局部性保留性能。然后，提出了一种称为NVD-DI的分布式索引结构以支持CNBNN查询处理。基于这种NVD-DI索引结构，提出了一种有效的CNBNN查询处理算法。CNBNN算法的最大优点在于：移动客户可以随时发起查询，每一个CNBNN查询均可以在一个广播周期内执行完毕。模拟实验表明，所提出的CNBNN方法在性能上优于基于D树的Naive方法。

目录

声明

1 绪论

1.1 课题背景、目的和意义

1.2 国内外研究概况

1.3 主要研究内容、预计需达到的要求和技术指标

1.4 本文研究内容及安排

2 路网中移动对象连续反向最近邻查询算法

2.1 问题描述和数据结构

2.2 CRNN算法

2.3 扩展到单色和双色数据集上的连续反向k近邻查询

2.4 结论

3 路网中可变速对象连续k近邻查询算法

3.1 问题定义、数据结构和路网距离计算

3.2 CUkNNPLS 算法

3.3 CUkNNMean 算法

3.4 结论

4 路网中无线广播环境下连续最近邻查询算法

4.1 问题描述

4.2 解决NBNN查询的一个直观的方法

4.3 NBNN 查询处理

4.4 CNBNN查询算法

4.5 性能评价

4.6 结论和未来工作

5 总结与展望

5.1 本文完成的主要研究工作及成果

5.2 本文主要的创新点

5.3 未来研究工作

致 谢

参考文献

附录1 攻读学位期间发表论文目录

附录2算法BVTAVC