Personalized Route Description Based On Historical Trajectories

With the fast development of mobile Internet and communication technology,navigation systems are widely used in people's daily life.The turn-by-turn route navigation information provided by existing navigation systems is mainly from road network topology,which is considered as a tool that can reduce measurement in physical world to simple oral descriptions(such as distance,time,steering etc.).Those navigation descriptions neglect people's inherent cognition of geographical layout,which are redundant for drivers who are familiar with the city.Current methods not only make navigation descriptions ambiguous for drivers but also occupy a large number of resources.The user navigation historical data contains a large amount of geographic information from the internet applications.Therefore,this thesis wants to find a new personalized navigation description algorithm that can make use of users' historical trajectory data to produce more concise,direct and accurate customized route descriptions.Thus navigation information becomes easier for the driver to understand.And personalized route description can use less resources(e.g.,screen space)to explain the entire route in a more intuitive way with high level informations.Based on the aforementioned problems,a personalized navigation route description algorithm called PerRD(Personalized Route Description)is proposed in this thesis,aiming to produce intuitively personalized route description for each user based on their historical trajectory.PerRD utilizes a large amount of historical trajectory information to extract routes frequently visited by customers in the road network.This thesis divides this task into following questions step by step.The first step is to explore the familiarity score as much as possible,and also to find optimal path segments while minimizing the number of route segments.The next step is to find appropriate location types and landmarks to generate a suitable sentence that describes every route segment.To prove the effectiveness,the methodology proposed in this thesis is exploited into the three trajectory datasets and real experiences of customers to evaluate PerRD performance and effectiveness.This thesis proposes a personalized navigation route description algorithm based on user historical trajectory called PerRD.The target of this algorithm is to provide city commuters with higher-quality personalized route descriptions by utilizing historical trajectory.This thesis formalizes the route description problems and provides effective algorithm to solve it optimally.A method to find the most appropriate location word to describe the route segmentation is proposed in this thesis.To the best of our knowledge,this thesis is the first one to use personalized location word to describe routes.Extensive experiments are conducted on real world datasets and a Web service to evaluate the performance and the effectiveness of the proposed PerRD.As the results shows,PerRD can reduce route description sentences and maintain great navigation services for users with an appropriate number of routes.