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

• 作者: 廖巍 景宁 赵亮 陈荦
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 移动对象 道路网 连续k近邻查询 多线程 频繁更新
• 年，卷（期）: 2010,（8）
• 页码范围: 1396-1404
• 分类号: TP392
• 字数: 7775字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.01396

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	廖巍	海军工程大学电子工程学院	37	253	8.0	14.0
2	景宁	国防科学技术大学电子科学与工程学院	86	1302	18.0	33.0
3	陈荦	国防科学技术大学电子科学与工程学院	59	604	14.0	22.0
4	赵亮	国防科学技术大学电子科学与工程学院	16	104	6.0	9.0