The Research Of Finding Most Frequent Path Based On Stratified Urban Roads

With the popularity of mobile devices,a large amount of trajectory data are accumulated.The path query based on big trajectory data has become a promising research.Most frequent path algorithm(MFP)is one of the classic path query algorithms based on trajectory data.It reconstructs a new graph using the trajectory data.The weight of an edge in MFP is defined as counting the number of the trajectories going through this edge.Though the path of MFP is in line with natives,it contains too many road intersections and too few high-level roads(such as highway,freeway),its time complexity is large and practicality is not strong.In order to solve the problems of MFP algorithm,this paper makes the following research:First this paper studies a new path query to find the most frequent path based on road levels in large-scale historical trajectory data(RLMFP).This algorithm is based on MFP and reduces the complexity of the algorithm utilizing the hierarchical road network of the existing city road level.The algorithm makes a high-level road network(the road network constructed only by highway or freeway)based on the existing road level.Then it uses breadth-first traversal algorithm to divide the whole road network into several small road networks according to the high-level road levels.This road network is stored by tree structure.Next algorithm computes the path through the technology of hierarchical network and MFP algorithm.Then this paper proposes RLMFPT to optimize RLMFP using the index structure of nested hash structure.In path query algorithm based on hierarchical road network,MFP cannot select appropriate upgrade points(the intersection between low-level roads and high-level roads)because it is an undirected path query algorithm.RLMFP should compute all paths from start point to each upgrade point,which is the cause of the instability of RLMFP.FG is an index table for each of any two regions to store a series of upgrade points of this region and the number being selected by trajectory data.It is helpful for RLMFP to choose the appropriate upgrade points.In outer hash table of FG,the combination of the IDs of two road networks(assumed the start point in A and the end point in B)is the key and the inner hash table of FG is the value.In the inner hash table of FG,the ID of one upgrade point in the area of start point(here is A)is the key.The number of trajectory which starting point is in A,end point is in B and passes that upgrade point is the value.This paper proves the rationality of these two algorithms(RLMFP and RLMFPT)by theoretical analysis.With the actual taxi trajectory data and simulated trajectory data,this paper illustrates the path being recommended by RLMFP or RLMFPT is more reasonable than MFP and the response time of these two algorithm is faster.But with the increase scale of the map,RLMFP is lack of stability in time complexity and has a great dependence to the number of upgrade points.And RLMFPT algorithm can overcome these disadvantages.