中文摘要：

已有道路网中的连续k近邻查询处理算法采用增量式的查询处理机制,当数据频繁更新时性能急剧下降.结合多核多线程技术,提出了一种基于多线程的连续查询处理框架.该框架周期性重计算所有查询结果,将查询处理分为顺序执行的数据更新阶段和查询执行阶段,分别使用任务并行和数据并行的方法执行各阶段的操作.设计了数据更新阶段使用的数据结构,提出了查询处理阶段的k近邻查询处理策略,包含离线预计算和在线k近邻查询处理算法两个部分.对k近邻算法复杂性及多线程处理框架的加速比进行了理论分析.实验结果表明,提出的算法在数据频繁更新下,串行执行时性能优于已有算法,而基于多线程处理框架的并行执行在任何参数配置下性能均优于已有算法;且基于多线程处理框架的并行执行具有较好的性能扩展性,加速比可以达到1.51～1.7.

英文摘要：

Existing algorithms for continuous k-nearest neighbor（kNN） queries of moving objects in road networks adopt the incremental query mechanism,which is verified to be inefficient when data update frequently.Considering the ubiquitous multi-core and multi-threading technologies,a multi-threading based framework for continuous kNN queries of moving objects is proposed.In the framework,all the queries are re-evaluated periodically,and the query process is divided into two sequential phases：the data updating phase and the query execution phase,task parallel and data parallel mechanism are used respectively in each phase to carry out the corresponding operations.In the updating phase,the data structures used in the framework are designed.Moreover,in the execution phase a kNN query strategy is proposed which includes an off-line pre-computation and an on-line query algorithm.The computational complexity of the algorithm and the speedup of the framework are analyzed theoretically.Experimental results show that,under the frequent update environment,the proposed query algorithm when serially executed has better performance than the traditional algorithms,however,the multi-threading based parallel execution is better in all kinds of parameter setups;what＇s more,the multi-threading based parallel execution maintains good performance scalability,and the speedup can reach to 1.51~1.7.