双流模式下高吞吐量移动对象范围查询算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61272138);中国人民大学科学研究基金(中央高校基本科研业务费专项资金资助)(10XNI018)


Throughput Oriented Range Query Algorithm for Moving Objects in Dual Stream Mode
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    随着位置感知移动设备的出现及通信技术和GPS系统的不断发展,基于位置的查询在数据库领域得到了广泛的关注.研究了基于快照的空间范围查询,即,查询在某个时间段位于某个查询范围内的移动对象.范围查询是其他空间查询的基础,例如KNN查询和反KNN查询等,很容易在范围查询的基础上得到.国内外的研究者针对移动对象的范围查询问题提出了一系列的算法,然而这些算法要么关注于解决移动对象的快速更新问题,要么关注于解决范围查询的快速处理问题.在大数据的背景下,查询和更新大量涌入时,不仅要求查询算法有较快的响应速度,还要求它们能够实现较高的吞吐量,但已有算法不能很好地解决高吞吐量的问题.针对移动对象更新数据流和查询数据流,提出一种基于内存的高吞吐量移动对象范围查询算法——双向流连接(DSJ)算法.双向流连接算法采用基于快照的模式,通过在每个快照中重新构建索引的方式,以避免复杂的索引维护操作,充分发挥了硬件的性能;通过每次执行一组查询的方式,增加了数据的局部性,提高了算法的效率;在执行过程中,通过使用SIMD技术以加速查询处理过程.基于以上几点,双向流连接算法能够确保整个系统具有很高的吞吐量.在基于德国路网生成的数据集上对算法进行了测试,实验结果表明,双向流连接算法具有很好的性能表现.

    Abstract:

    With the development of location-aware mobile devices, communication technologies and GPS systems, location based queries have become an important research issue in the area of database. This paper studies the problem of snapshot based spatial range query which searches for the moving objects within a specific query range in a specific time interval. Range query is the building block of other types of spatial queries, such as k nearest neighbor query and reverse k nearest neighbor query. A series of algorithms have been proposed to process range queries of moving objects. However, these algorithms are either designed for fast response time or high update performance. They are not purposely designed for the situation of big data where throughput is more important as both queries and updates arrive at a very high rate. For the query stream and object update stream, a high throughput main memory algorithm—Dual Stream Join algorithm is proposed for moving object range query. DSJ uses a snapshot approach. In each snapshot, DSJ builds a new index structure based on the update of the moving objects, which avoids maintaining a sophisticate structures and gives full play to the performance of the hardware. DSJ executes a batch queries at each run, which increases the data locality and improves the efficiency of the algorithm. DSJ also employs the SIMD technology to accelerate the query processing and makes sure that the system has high throughput. A comprehensive performance evaluation of the proposed techniques is conducted using the German network generated data. The results show that DSJ is highly efficient.

    参考文献
    相似文献
    引证文献
引用本文

薛忠斌,周烜,王珊.双流模式下高吞吐量移动对象范围查询算法.软件学报,2015,26(10):2631-2643

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2014-06-07
  • 最后修改日期:2014-12-09
  • 录用日期:
  • 在线发布日期: 2015-10-10
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号