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

Throughput Oriented Real-time Query Processing Algorithm for Moving Objects in Road Network

作　　者：薛忠斌[1,2,3] 白利光 何宁 周烜[2,3] 周歆[2,3] 王珊[2,3] XUE Zhong-bin BAI Li-guang HE Ning ZHOU Xuan ZHOU Xin WANG Shan(Guohua （Beijing） Electric Power Research Institute Co. Ltd, Beijing 100069, China MOE Key Laboratory of Data Engineering and Knowledge Engineering （Renmin University of China） ,Beijing 100872 ,China School of Information, Renmin University of China, Beijing 100872, China)

机构地区：[1]神华国华(北京)电力研究院有限公司,北京100069 [2]教育部数据工程与知识工程重点实验室(中国人民大学),北京100872 [3]中国人民大学信息学院,北京100872

出　　处：《计算机科学》2017年第3期16-19,41,共5页Computer Science

摘　　要：随着无线通信技术、空间定位技术和移动计算技术的快速发展,基于位置的查询成为数据库领域的一个重要研究问题。研究了路网中移动对象的KNN查询,一系列的算法被提出用于解决移动对象的KNN查询问题。然而,这些算法关注于查询的快速响应问题或者专注于解决移动对象的快速更新问题。随着移动对象数量的不断增加,当查询和更新大量涌入时,吞吐量成为一个更重要的问题。针对移动对象的更新数据流和查询数据流,提出了一种基于内存的高吞吐量移动对象KNN查询算法——DSRNKNN算法,用于处理路网中移动对象的KNN查询。DSRNKNN算法采用了基于快照的模式。在每个快照中,DSRNKNN算法通过重新构建索引的方式避免了复杂的索引维护操作,充分发挥了硬件的性能;通过每次执行一组查询的方式,充分利用查询内和查询间的并行,增加了数据的局部性,提高了算法的效率。在基于实际路网生成的数据集上对算法进行了测试,实验验证了DSRNKNN算法具有很好的性能表现。With the rapid development of wireless communication technology, space positioning technology and mobile computing technology,location based queries have become an important research issue in the area of database. In this paper, we studied the problem of moving object KNN query in road network. A series of algorithms have been proposed to process KNN queries of moving objects. However, these algorithms are either designed for fast response time or high update performance. With the increasing of moving objects, when both queries and updates arrive at a very high rate, the throughput becomes more important. For the query stream and object update stream, we proposed a high throughput main memory algorithm dual stream road network KNN （DSRNKNN） algorithm, which is used for moving object KNN query in road network. DSRNKNN uses a snapshot approach. In each snapshot, DSRNKNN builds a new index structure based on the update of the moving obiects, which avoids complex index maintenance operations and gives full play to the performance of the hardware. DSRNKNN executes a batch queries at each run,making full use of inner-and inter-parallel, which increases the data locality and improves the efficiency of the algorithm. We conducted a comprehen- sive performance study of the proposed techniques by using the real network generated data. The results show that DSRNKNN is highly efficient.

关 键 词：时空数据库 移动对象 KNN查询 主存 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]