可伸缩的道路网络多连续k近邻查询处理

Scalable processing of multiple continuous k nearest neighbor queries in road networks

针对基于道路网络的多用户连续k近邻查询处理,提出了一种可伸缩的多用户连续查询处理(scalable processing ofmultiple continuous queries,SPMCQ)框架。SPMCQ框架采用流水线处理策略,将连续k近邻查询执行分解为可同时作业的预处理、查询执行和结果分发3个阶段,利用多线程技术提高查询处理的并行性。基于SPMCQ框架,分别利用基于内存的哈希表和线性链表结构对移动对象位置和道路网络有向图模型进行存储和管理,提出了多连续k近邻查询处理SCkNN算法。实验结果表明,在处理多用户连续k近邻查询时,该算法性能优于目前的道路网络连续k近邻查询处理算法。

In order to efficiently process multiple continuous k nearest neighbor queries in road networks,a scalable processing of multiple continuous queries（SPMCQ） framework is proposed,which exploits pipeline strategy and decomposes the executing progress into three stages： Preprocessing,executing,and dispatching to improve the computing parallelism with multi-threading methods.SCkNN algorithm is presented based on SPMCQ frame using in-memory hash table and linear list structures to store the moving objects and describe the directional model graph respectively.Experimental results show that our algorithm outperforms existing algorithms when processing multiple continuous nearest neighbor queries.