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

作     者：赵亮 陈荦 景宁 廖巍 ZHAO Liang;CHEN Luo;JING Ning;LIAO Wei

作者机构：国防科学技术大学电子科学与工程学院长沙410073 海军工程大学电子工程学院武汉430033 

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

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2010年第33卷第8期

页      码：1396-1404页

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

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

学科分类：0810[工学-土木类] 0808[工学-自动化类] 0839[0839] 081203[081203] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3724/sp.j.1016.2010.01396

馆 藏 号：203549084...