Research On The Processing Of Route Planning Queries With Keywords Search

With the growth of travel demand and the expansion of city size,more and more people are relying on navigation and route planning applications to assist in travel.In route planning,users usually need to search for routes related to specific keywords,which can also be expressed as using keywords to constrain route planning.Based on this demand,route planning queries that support keyword search have emerged.In the existing research on solving route planning query problems that support keyword search,the algorithm results are usually divided into two situations: approximate routes and accurate routes.The approximation algorithm uses approximation techniques to query routes,so its calculation results cannot be accurately guaranteed.In scenarios that require highprecision route planning,this loss of accuracy may be unacceptable.In precise algorithms,due to the need to simultaneously consider multiple factors such as route length,road traffic conditions,points of interest,etc.in the path planning problem of keyword search,the algorithm required to solve this problem requires a large amount of computation,and requires a lot of time and computational power when processing large-scale data.To solve the above problems,this thesis proposes a top-k routes search algorithm by supporting keyword search,which considers both the shortest distance of the route and the user’s rating of interest points,and provides users with personalized travel solutions by selecting k routes with short distances and high ratings.The core idea of the algorithm is to divide the road network into subgraphs and adopt a heuristic search strategy to gradually expand the search area from the subgraph where the user starts from to the adjacent subgraphs,and introduce a subgraph pruning strategy and a sequence of interest points pruning strategy to improve the search efficiency.When expanding to a new subgraph,the traversal of invalid subgraphs is avoided by judging whether the interest points of the new subgraph and the existing interest points can generate routes that can update the set of candidate routes.For a set of interest points to be processed,the upper bound of the score of the set of interest points is obtained using the Euclidean distance,and the sequence of interest points that are unlikely to be candidate routes is pruned using the upper bound of the score,thus further reducing the number of computed candidate routes on the basis of subgraph pruning.This solution can greatly improve the travel efficiency and travel experience of users.Finally,this thesis conducts experiments on four real road network datasets with three benchmark algorithms to verify the superiority of the proposed algorithm.Second,in order to improve the search speed of the solution space,based on the above algorithm,this thesis proposes a parallel top-k routes search algorithm by supporting keyword search,which introduces a subgraph parallel pruning strategy and a sequence of interest points parallel pruning strategy to improve the speed of searching the solution space.When expanding from the subgraph where the user’s starting point is located to the adjacent subgraphs,the adjacent subgraphs are parallelized,while judging whether the interest points of the new subgraph and the existing interest points can generate routes that can update the set of candidate routes,and the unpruned subgraphs send their interest points to the interest point processing node in real time to complete the information transfer between the subgraphs.After that,the set of interest points to be processed is assigned to different processing nodes,and the upper bound of the score generated by the route processing nodes is constantly compared with the lower bound of the score generated by the set of candidate routes,and finally the computed results are combined to obtain the global top-k routes.Finally,this thesis conducts experiments on four real road network datasets with the top-k routes query algorithm supporting keyword search.The experimental results show that through parallel computing and targeted optimization,the efficiency of top-k routes query with keyword search support is significantly improved and the query response time is significantly shortened,which is of practical value for real application scenarios.