路网中高吞吐量移动对象实时查询算法

• 作者: 何宁 周歆 周烜 王珊 白利光 薛忠斌
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 时空数据库 移动对象 KNN查询 主存
• 年，卷（期）: 2017,（3）
• 所属期刊栏目: 2015全国高性能计算学术年会
• 页码范围: 16-19,41
• 页数: 5页
• 分类号: TP301
• 字数: 5364字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2017.03.004

摘要

随着无线通信技术、空间定位技术和移动计算技术的快速发展,基于位置的查询成为数据库领域的一个重要研究问题.研究了路网中移动对象的KNN查询,一系列的算法被提出用于解决移动对象的KNN查询问题.然而,这些算法关注于查询的快速响应问题或者专注于解决移动对象的快速更新问题.随着移动对象数量的不断增加,当查询和更新大量涌入时,吞吐量成为一个更重要的问题.针对移动对象的更新数据流和查询数据流,提出了一种基于内存的高吞吐量移动对象KNN查询算法——DSRNKNN算法,用于处理路网中移动对象的KNN查询.DSRNKNN算法采用了基于快照的模式.在每个快照中,DSRNKNN算法通过重新构建索引的方式避免了复杂的索引维护操作,充分发挥了硬件的性能;通过每次执行一组查询的方式,充分利用查询内和查询间的并行,增加了数据的局部性,提高了算法的效率.在基于实际路网生成的数据集上对算法进行了测试,实验验证了DSRNKNN算法具有很好的性能表现.