双流模式下高吞吐量移动对象范围查询算法

来源：软件学报杂志2015年第10期北京时间：

作者：薛忠斌,周烜,王珊

单位：薛忠斌，教育部数据工程与知识工程重点实验室中国人民大学, 北京 100872;中国人民大学 信息学院, 北京 10087211,周烜，教育部数据工程与知识工程重点实验室中国人民大学, 北京 100872;中国人民大学 信息学院, 北京 10087202,王珊，教育部数据工程与知识工程重点实验室中国人民大学, 北京 100872;中国人民大学 信息学院, 北京 10087203

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

关键词：大数据;时空数据库;移动对象;范围查询;主存

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