Research On Direction-aware Query Processing On Moving Objects In Road Networks

The range query and KNN query on moving objects are classical query methods in road networks,which have been widely used in many fields.However,there are still some deficiencies in the existing query methods for processing on moving objects in road networks.On one hand,most of them only consider the network distance,and pay less attention to the direction of moving objects’ movement in road networks;on the other hand,a few query methods that consider the direction of movement are based on Euclidean space and unable to determine whether the objects move toward the query point or not in large scale complex road networks.Because it is a extremely time-consuming process to determine the direction of moving objects in road networks by using the existing methods.For the problem of accurately and efficiently finding objects moving towards the query point in large scale complex road network,this paper adequately analyzes the existing query methods for processing on moving objects in road networks,considers R-tree and simple grid as a support,presents an efficient decision method for objects moving towards an query point and proposes a direction-aware range query and a direction-aware KNN query for moving objects in road network,which can quickly find the target objects that move towards the query point in large-scale road networks.The main contents of this paper include:(1)In order to perceive whether the object is moving towards the query point in a large-scale complex road network,this paper designs the method of determining the moving object of the road network towards the query point based on incremental network expansion.The direction of movement of the moving object is opposite to that of the road network,and the moving object is the moving object facing the query point.(2)In order to improve the query efficiency of moving objects in road networks,the paperputs forward the scheme of dual indexes.Considering the "static" characteristics of the road network and the "dynamic" characteristics of the moving objects,combining the R-tree’s efficient and stable query performance and the grid index’s insensitive updating,we use the R-tree to index the road network and the simple grid to index moving object.(3)The paper proposes a direction-aware range query algorithm for moving objects in road networks to find out all objects nearby moving towards the query point.With the support of dual indexes,under incremental network expansion and using the moving object determination method,the direction-aware range query algorithm is implemented efficiently.In order to evaluate the performance of the range query algorithm,we experiment on three arguments including the query scope,the number of moving objects and the number of girds.The experimental result shows that the direction-aware range query algorithm performance well when the arguments are set suitable.(4)In order to have the further solution of querying k nearest neighbors of objects moving towards query point in road networks,this paper proposes the direction-aware k nearest neighbors query algorithm.It first uses a query scope gradual detection algorithm to evaluate a suitable search space,and then performs a incremental network expansion locally in the search space while utilizing the moving object determination method to screen out k nearest neighbors moving towards the query point.We experiment on four arguments including the number of nearest neighbors,the number of moving objects,the number of grids and the detection coefficient.The experimental result shows that the direction-aware k nearest neighbors query algorithm is efficient when the arguments are set suitable.