时间依赖路网中连续k近邻查询处理技术研究

Continuous k nearest neighbors (kNN) queries monitoring in road networks have attracted significant research interest over the past few years. However, the proposed algorithms are only applicable to the static road networks where the weights on the edges are constants, but inapplicable to the time-dependent road networks, where the weights of edges are functions over time due to the traffic conditions. Continuous k nearest neighbors queries in time-dependent road networks shows great potential prospect in smart navigation, location based advertisements, emergency rescue and so on. When considering time-dependency of networks, the kNN query results depend on the location of the query as well as the query time, which makes it difficult to choose the best path and monitor the kNN query results. Monitoring continuous kNN queries in time-dependent road networks poses great challenges on the index of road networks, the pruning strategies of kNN queries, the continuous monitoring of the query results and the control of quality of service. Little work has been reported on supporting continuous kNN queries in time-dependent road networks. Based on the features of the time-dependent road networks and kNN queries, this application deeply studies the model and the update strategies of the index, the pruning strategies for kNN queries, the continuous monitoring of the query results, the evaluation model and load shedding of quality of service.

尽管基于路网环境的连续k近邻查询处理技术已经取得了丰富的研究成果，但这些成果主要针对权值是常量的静态路网应用环境，无法直接应用到权值是动态变化的时间依赖路网中。在时间依赖路网中，由于受到路况条件或交通事故的影响，路网中边的权值随着时间变化而改变。时间依赖路网下连续k近邻查询在智能导航、位置广告、紧急救援等领域展现了广阔的应用前景。查询结果不仅与查询点的位置有关，还与发出查询的时间有关，道路网中出行路径的选择以及连续k近邻的计算过程变得更加复杂。这对路网的索引技术、连续k近邻查询处理技术以及连续查询服务质量控制技术提出了新的挑战。目前，针对时间依赖路网下连续k近邻查询的研究较少，本申请针对时间依赖网络以及连续k近邻查询的特点，深入地研究相关的路网索引模型与索引更新策略、k近邻查询的多种剪枝策略、连续查询的结果维护策略，以及服务质量的评价模型与卸载策略等问题。

近邻及近邻相关查询做为时空数据库中重要的查询类型，在欧氏空间和路网空间中被广泛研究。但在边权值是动态变化的时间依赖路网环境中，研究成果较少。由于边权值随着时间的改变而变化，路网中两点间的代价计算变得复杂，已有技术不能直接应用在时间依赖路网中的近邻查询问题中。本项目针对时间依赖路网中连续k近邻查询的特点，深入地研究了：（1）时间依赖路网索引模型与索引更新策略；（2）时间依赖路网k近邻以及相关查询的多种剪枝策略、连续查询的结果维护策略；（3）查询服务质量优化；（4）数据产生及结果展示原型系统。主要成果如下：.（1）索引结构：利用网格，提出了基于兴趣点分布的合并策略，设计了时间依赖路网索引结构，使范围查询、近邻查询和最快路径查询，响应时间减少了34%到60%。.（2）k近邻及相关查询：a）提出了基于动态选择启发值的k近邻改进算法，使查询响应时间减少了47%；b）基于预计算和在线扩展结合的方式，提出了k近邻查询优化方法，响应时间减少了40%；c）提出了基于子网划分的反向k近邻查询算法，解决了已有算法在兴趣点分布稀疏时，查询效率低的问题，比已有算法遍历结点数少50%；d）针对概率剪枝阶段子区域划分粒度无法动态调整的问题，提出了基于分类的概率组近邻查询优化算法，响应时间减少了2-3倍；e）针对单次快速k近邻查询无法有效解决连续k近邻查询的问题，提出了基于分割点的连续查询结果计算和维护算法，响应时间上减少了近一个数量级。.（3）查询服务质量优化：基于出租车轨迹数据，考虑时间、是否工作日、天气、交通异常数据、相邻路段之间相互影响的因素，对行驶时间函数进行了预测，提高了传统方法的预测精度，进而提高了服务质量。.（4）原型系统：利用JAVA技术，开发了时间依赖路网仿真系统，系统可根据不同的工作日、时间、天气、兴趣点类型等参数，为科研人员生成多种时间依赖网络数据集。还能够通过预留的算法接口，在地图上显示出不同查询的结果。