主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2020年专刊出版计划 微信服务介绍 最新一期:2019年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
赵亮,景宁,陈荦,廖巍,钟志农.面向多核多线程的移动对象连续K 近邻查询.软件学报,2011,22(8):1805-1815
面向多核多线程的移动对象连续K 近邻查询
Continuous K Nearest Neighbor Queries over Moving Objects Based on Multi-Core and Multi- Threading
投稿时间:2009-08-17  修订日期:2010-03-04
DOI:10.3724/SP.J.1001.2011.03904
中文关键词:  移动对象  连续K 近邻查询  多核多线程  cache 优化  查询分组
英文关键词:moving object  continuous KNN query  multi-core and multi-threading  cache optimization  query grouping
基金项目:国家自然科学基金(40801160, 60902036); 国家高技术研究发展计划(863)(2008AA12A211); 中国博士后科学基金(20080431384)
作者单位E-mail
赵亮 国防科学技术大学 电子科学与工程学院,湖南 长沙 410073
空军装备研究院 通信所,北京 100085 
liangzhao2010@gmail.com 
景宁 国防科学技术大学 电子科学与工程学院,湖南 长沙 410073  
陈荦 国防科学技术大学 电子科学与工程学院,湖南 长沙 410073  
廖巍 海军工程大学 电子工程学院,湖北 武汉 430033  
钟志农 国防科学技术大学 电子科学与工程学院,湖南 长沙 410073  
摘要点击次数: 3717
全文下载次数: 3263
中文摘要:
      针对移动对象的多用户连续K 近邻查询处理问题,结合多核多线程技术的发展,提出了一种基于多线程的两阶段多用户连续K 近邻查询处理框架.将查询处理分为查询预处理阶段和查询执行阶段,分别执行数据更新任务和查询处理任务.每个阶段都设计了优化cache 访问命中率,并利用多线程技术提高多用户连续查询处理并行性的方法及数据结构.提出了一种查询执行阶段的查询分组技术,利用查询之间的相关性提高了算法执行时内存访问的时间局部性.基于查询处理框架和移动对象内存格网索引结构提出了K 近邻查询处理算法.充分的实验结果表明,采用了多线程和cache 优化技术的连续查询处理框架与其他算法相比,在性能上具有较大优势,并且在不同核心数目的CPU 平台下具有较好的性能扩展性.
英文摘要:
      To solve the problem of multiple continuous K nearest neighbor (KNN) queries over moving objects, considering the development of multi-core and multi-threading technologies, a two-stage framework is proposed for Multi-Threading Processing of Multiple Continuous KNN Queries (MPMCQ). This includes a preprocessing stage and a query execution stage to carry out the data updating task and the query execution task separately. In each of the stages, techniques are designed to optimize the cache access hit ratio and improve the parallelism through multi-threading. A query grouping technique in the query execution stage is proposed to improve the data temporal locality when accessing the memory. Thus, the cache hit ratio can be guaranteed. A KNN query algorithm is given based on the MPMCQ framework and the grid index for moving objects. Extensive experiments are carried out to verify that by adopting the multi-threading and the cache optimization technologies, the proposed framework implements a much superior performance than other famous algorithms; moreover, it maintains excellent performance scalability when executed under different multi-core CPUs.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利