《计算机学报》文章摘要   全文下载
文章题目	道路网中的移动对象连续K近邻查询
作者	赵亮1) 陈荦1) 景宁1) 廖巍2)
作者单位	1)(国防科学技术大学电子科学与工程学院 长沙 410073) 2)(海军工程大学电子工程学院 武汉 430033)
发表年份	2010
发表月份	8期(1396—1404)
文章摘要	摘要 已有道路网中的连续k近邻查询处理算法采用增量式的查询处理机制，当数据频繁更新时性能急剧下降.结合多核多线程技术，提出了一种基于多线程的连续查询处理框架.该框架周期性重计算所有查询结果，将查询处理分为顺序执行的数据更新阶段和查询执行阶段，分别使用任务并行和数据并行的方法执行各阶段的操作.设计了数据更新阶段使用的数据结构，提出了查询处理阶段的k近邻查询处理策略，包含离线预计算和在线k近邻查询处理算法两个部分.对k近邻算法复杂性及多线程处理框架的加速比进行了理论分析.实验结果表明，提出的算法在数据频繁更新下，串行执行时性能优于已有算法，而基于多线程处理框架的并行执行在任何参数配置下性能均优于已有算法；且基于多线程处理框架的并行执行具有较好的性能扩展性，加速比可以达到1. 51~1. 7. 关键词 移动对象；道路网；连续k近邻查询；多线程；频繁更新 中图法分类号 TP392 DOI号：10.3724/SP.J.1016.2010.01396