Time-Based Road Network Keyword Query And Route Planning

With the increasing travel demand of people and the upgrading of mobile smart communication devices,location-based services have developed rapidly.In daily life,people use map applications to query destinations and plan travel routes.This function combines the ideas of spatial keyword query and route planning.In recent years,the spatial keyword query has been extended from European space to the road network,and the path planning has been extended from static target points to dynamic target points.However,the existing spatial keyword query technology and road network path planning method in European space and road network focus on the location information and text description of target points,which is difficult to meet the growing personalized and diversified needs of users.We know that the text description of each object in the road network is not unique and it is not valid for every time period.For example,restaurants usually open in the daytime and bars open at night.There are also many differences in business hours between objects with the same text information.For example,some restaurants open late while others close early.It can be seen that time is a very important factor.Taking the time factor into account in keyword query and route planning can better meet the needs of users.Therefore,this dissertation studies the spatial keyword query and route planning problem on time-based road networks.Firstly,in order to facilitate the distance calculation of objects in the road network,as well as the reasonable organization and rapid acquisition of object text and time information,a new index structure named IGT-Tree is built based on the ideas of G-Tree and IR~2-Tree.In this paper,the valid time dimension is added to the objects in the road network,represented by timestamps,and the location,keywords and effective time are specified for each object.In addition,the text information,location information and time information of objects are matched with the query point to retrieve the target objects,and the corresponding pruning strategies for the IGT-tree node are proposed.Based on the IGT-Tree index structure and pruning strategies,this paper designs the single-target keyword query algorithm Rnkq(Road network keyword query),which enables users obtain the best target object by setting the query keyword.At the same time,the single-objective path planning algorithm Sopp(Single-objective path planning)is designed to recommend the best path from the query point to the target point for users,so as to minimize the distance cost for users to reach the target object.Then,this dissertation studies the path planning of multiple target points in the road network.When the user gives multiple query keywords,the target object will not be unique.At this time,multiple target objects that meet the query requirements on the road network should be selected,and a path should be recommended to make the distance cost for the user to pass through all the target objects close to the minimum.Based on the IGT-Tree index,four path recommendation algorithms are designed to solve the path planning problem of multi-target keywords,including multi-objective sequential path recommendation algorithms,namely Cssp(Complex sequential sorting path algorithm)and Ssp(Sequential sorting path algorithm),and multi-objective disordered path recommendation algorithms,namely Cdpp(Complex disordered path planning algorithm)and Dpp(Disordered path planning algorithm).Finally,a series of comparative experiments are carried out on CA and SF,two synthetic datasets based on real road networks.The experimental results show that the IGT-Tree based algorithms are more accurate than the G-Tree based algorithms in keyword query and path planning on time-based road networks.In addition,the time cost of the proposed algorithms is compared to verify the efficiency of the proposed IGT-Tree indexing and query processing algorithms in the time-based road network.