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

Continuous K Nearest Neighbor queries(CKNN),which are a variant of the K Nearest Neighbor queries(KNN),are to find the K data objects with minimum cost for each point on a specified path.At present,the researchers only study the CKNN problem in Euclidean space and static road networks.However,in real life,the weight of the edge is a dynamic value that changes with time.The traditional technology for CKNN on the static road networks cannot be directly applied for the dynamic environment.In this paper,CKNN are further studied in time-dependent road networks where the edge weights vary dynamic with time.This thesis defines and solves the problem of Continuous K Nearest Neighbor queries in time-dependent road networks(TD-CKNN).A Split Point based(SPB)algorithm with two-phases for TD-CKNN are proposed by using the nature of the integral and merging weighted functions.The SPB algorithm includes a filtering phase and a refinement phase.In the filtering phase,a method is proposed for calculating the arrival time of the node.Then,the arrival time is used to obtain the candidate K Nearest Neighbor results.Moreover,a pruning-based continuous path query algorithm is utilized to verify whether the path to the respective multiple data objects are the same as the path to the data objects for each endpoint at the corresponding time interval,which is the time interval from the start node to the end node of the subsection.In the refinement phase,all the weights from the query points to the candidate results are merged,and the split points can be obtained by calculating the intersection of the functions.Since the results of the two endpoints may be the same for the sane road segment,the SPB algorithm is executed on each subsection.After running SPB,several split points and K Nearest Neighbor results in the corresponding interval can be obtained.Based on the real Oldenburg city road networks,the simulation data set is used to compare the performance of the Naive algorithm for multiple snapshot K Nearest Neighbor queries and the SPB algorithm proposed in this paper.The experimental results show that under various experimental settings,the SPB algorithm is nearly an order of magnitude smaller than the Naive algorithm in response time.