Splicing Active Trajectory Pairs Search Based On Range

With the development of geolocation technology and location-based services,a large amount of trajectory data has been generated,and the trajectory with activity message has attracted wide attention.Active trajectory search based on range,given a query area and a set of keywords,retrieves the trajectory from the trajectory data set that passes through the area and satisfies the keyword.Because the return trajectory is too expensive to travel or the trajectory is not popular enough,the trajectory is not satisfactory to the user.Therefore,in order to meet the needs of users,this paper takes into account the popularity of keywords and trajectory spliced.A new query is proposed,which gives the comprehensive evaluation function of travel cost and trajectory popularity,and returns the best splicing trajectory pairs with the values of top-k evaluation functions under the constraints of a given region and keyword text.Firstly,proposes the definition of the splicing active trajectory pairs query based on the range,and three kinds of index structures to solve the query,which are grid keyword inversion index,splicing trajectory pair index and raw trajectory index respectively.On the basis of these indexes,proposes a naive algorithm based on the range,which firstly finds out the trajectory with query keywords and then traverses any two trajectories to find out the trajectory pairs that can cover query keywords.Finally,the best splicing trajectory pairs of the Top-k evaluation function values are returned to the user.Secondly,according to the naive algorithm proposed,proposes three optimization algorithms.The optimization algorithm based on cover keywords processes keywords in advance,finds out the combination of trajectory pairs that can cover the keywords,and then calculates the evaluation function value of the splicing trajectory pairs in each combination.Optimization algorithm based on upper limit of score after obtaining a splicing trajectory pairs that can cover the query keywords,delays the calculation of the travel cost of the trajectory,obtains the score upper limit of each pair of splicing trajectory,and terminates the query in advance when the upper limit is not greater than the best value of the evaluation function of the k trajectory pair of the current result.Optimization algorithm of upper limit of score based on single trajectory,while deferring the calculation of travel cost,obtains the upper limit of score obtained from each trajectory,and gives an effective clipping strategy to cut out the trajectory pairs that cannot be the result in advance.Finally,empirical analysis on real data set verifies the validity of our approaches.