Research And Implementation Of Nearest Neighbor Query Processing Technology In Time-dependent Road Networks

Most of the researches on the neighbor query services in road network are based on the Euclidean distance or road network distance.However,in practical applications,people pay more attention to the cost of travel time.The K-nearest neighbor query is widely used among the neighbor query services in the road network.Therefore,this paper studies the K-nearest neighbor query in the time-dependent road network,which is searching for K points of interest that the query point to reach K points of interest have the least time in the road network of which edge weights change over time.According to the accuracy of search result,the K-nearest neighbor query can be divided into accurate K-nearest neighbor query and approximate K-nearest neighbor query in time-dependent road network.Firstly,to solve the problem of low query efficiency on the existing K-nearest neighbor accurate query algorithm in time-dependent road network,the Precomputation Best-first algorithm(PreBF)is proposed,which is an accurate K-nearest neighbor query algorithm based on preprocessing and pruning.In the preprocessing phase,the node can quickly find the nearest neighbor at any moment by computing the nearest neighbor information list of the node.In the online computing phase,the nearest neighbor of the query point and the extended nodes are obtained by using the nearest neighbor information list of the node,which are used as the K-nearest neighbor candidate set of the query point,and then the candidate set is corrected according to the pruning technique.Compared with the classical TD-NE algorithm,the response time of PreBF is reduced by 26.7% and the number of nodes of PreBF is reduced by 26.84% on average.Experiment results show that PreBF algorithm reduces the number of nodes in query expansion,decreases the searching time,and improves the query efficiency.Secondly,this paper improves the Time Dependent Fast Travel Time(TD-FTT)algorithm,the K nearest neighbor query algorithm of higher query efficiency.The TD-FTT algorithm requires that the issued time and the arrivel time of a query must be in the same interval and the cost of processing time is great.To solve these problems,an improved TD-FTT(ITD-FTT)algorithm based on dynamically selecting the heuristic value is proposed and the nearest neighbor of the node is calculated by using the Network Voronoi Diagrame in parallel to reduce the computational time of the preprocessing stage.Experiment results show that the ITD-FTT algorithm improves the query efficiency of the TD-FTT algorithm and the calculation time is reduced by 70.12% in the preprocessing phase.Finally,we put foreard two algorithms,Approximate Precomputation Best-first algorithm(A-PreBF)?Precomputation Immediately algorithm(PreImd),based on the nearest neighbor information list of the nodes.Precomputation Fast Travel Time algorithm(Pre-IFTT)is proposed by combining pre-computation with heuristic.The accuracy of the three algorithms is guaranteed between 81.46% and 86.42%.