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

Abstract: 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 objects,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 comprehensive performance study of the proposed techniques by using the real network generated data.The results show that DSRNKNN is highly efficient.

Key words: Spatial temporal database,Moving object,KNN query,Main memory