移动对象连续κ近邻查询处理技术研究

摘要

基于位置的服务(LBS)是指通过移动终端和无线通讯网络的配合，确定用户具体所在的空间位置，从而为用户提供与空间位置相关的信息服务，如导航服务、交通调度、物流管理、紧急呼叫、位置广告等。基于位置的服务通常涉及到对大量移动对象的查询，k近邻(kNN)查询就是其中最为重要的查询之一。
　　 七近邻查询在解决实际应用中的需求越来越明显，引起了相关研究领域的广泛关注。目前，针对欧式空间中静态对象的k近邻查询技术已发展成熟，对于道路网环境，且考虑移动对象的连续七近邻(CkNN)查询处理技术的研究还很少，且已有的查询处理技术在面对大量并发查询时，效果并不太理想。
　　 本文是针对道路网环境下的移动对象连续七近邻查询处理技术展开的研究，目的在于尽可能地提高服务器端的查询处理效率，从而缩短查询响应时间。所做的工作主要体现在以下几个方面:
　　 (1)深入剖析了已有的基于欧式空间的和道路网环境下的移动对象连续k近邻查询处理的经典算法，对其一般性技术思路进行了概括，并讨论了各种查询处理方法的优缺点。比较了道路网环境和欧式空间查询处理的不同，总结了道路网环境下七近邻查询处理的难点。
　　 (2)经分析道路网环境下k近邻查询的特点，设计了一种共享计算的初始结果计算算法，在查询处理中，充分复用其他查询的计算成果，从而避免了对道路网的冗余搜索。实验验证了该算法在查询密集型道路网中的高效性。
　　 (3)面向高度动态的道路网环境，提出了一种基于扩展树的连续k近邻查询处理方法(TL-CkNN)，该方法周期性地对系统中的查询进行结果维护，通过应用数据更新进行扩展树剪枝，然后基于剪枝后扩展树中剩余的有效部分继续进行结果重计算，从而减少了对道路网的重复扩展。实验证明了算法在高度动态的道路网环境下的优越性。

目录

声明

摘要

图表清单

1 绪论

1．1 研究课题背景和意义

1．2 研究现状

1．2．1 移动对象索引技术

1．2．2 查询处理技术

1．3 存在问题和难点

1．4 本文研究内容

1．5 本文结构安排

2 连续k近邻查询处理技术分析

2．1 k近邻查询架构

2．2 基于欧式空间的连续k近邻查询处理

2．2．1 YPK-CNN算法

2．2．2 SEA-CNN算法

2．2．3 CPM算法

2．3 基于道路网的连续k近邻查询处理

2．3．1 IMA／GMA算法

2．3．2 ER-CkNN算法

2．4 本文技术思路

2．5 小结

3 基于IMA改进的连续k近邻查询处理

3．1 问题描述

3．2 数据结构

3．3 查询处理策略

3．3．1 TL-CkNN算法

3．3．2 网络扩展

3．3．3 扩展树复制

3．3．4 预处理

3．3．5 初始结果计算算法

3．3．6 移动对象位置更新

3．3．7 查询点位置更新

3．3．8 道路边权值更新

3．3．9 结果维护

3．4 小结

4 实验设计与分析

4．1 移动对象产生器

4．2 实验方案

4．3 结果分析

4．4 小结

5 结论与展望

5．1 结论

5．2 下一步工作

参考文献

致谢

个人简历、在学期间发表的学术论文