道路网中的移动对象连续K近邻查询

摘要：

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

关键词：移动对象、道路网、连续k近邻查询、多线程、频繁更新

所属期刊栏目：33

分类号：TP392(计算技术、计算机技术)

资助基金：国家自然科学基金40801160,60902036;国家"八六三"高技术研究发展计划项目基金2008AA12A211;中国博士后科学基金项目20080431384

在线出版日期：2010-10-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1396-1404