Research On Efficient Keyword-aware Optimal Route Query Processing Method

Searching an spatial route on a road network is a fundamental functionality in map services.Different from the shortest path search in traditional map service,the keyword-aware optimal route search,denoted as KORS,retrieves a route covering all the query keywords given by users,satisfying a certain budget constraint,while optimizing the cost spend on this route.KORS is a query type appeals to location-based-service(LBS),and can support travel route planning under user's preference.However,due to the features of multi-criterions,diversified expansion chooses and constrainted requirements in the query,the search work of an exact optimal route in KORS is NP-hard.Thereby,proposing more effective query processing methods is considerably challenging.In order to alleviate the complexity of solutions to a KORS query,the most state of the art method focuses on two approximation algorithms and a greedy algorithms to solve the KORS processing under a reduced search space.However,this method still has some problems,mainly reflected on two aspects:1)the efficiency overhead in the approximation approaches will be worse when the query is processed on a large-scale graph or the number of query keywords is increasing;2)query results retrieved by the greedy approach can not completely satisfy all the hard query constraints causing its poor usability.Therefore,in this paper,we start our work for the sake of alleviating above mentioned issues.After analyzing the feasible results of KORS,we find that the essence of KORS work is to process the connections between some query keyword related vertexes by skyline routes.As both of these methods adopts extreme route expansion strategy in the search process,respectively,with the tradeoff between efficiency and accuracy,we propose a state-of-the-art route expansion strategy: Keyword-aware Skyline Route Generation,denoted as KSRG,which uses skyline route expansion to replace extreme expansion ways in the previous work,and generate feasible routes satisfying query keyword coverage in the first place.For a scalable running of KSRG process,we further propose an appropriate Fully Polynomial Time Approximation Scheme(FPTAS),by which the complexity of the naive KSRG can be reduced into a polynomial order from the original factorial order.Based on the above framwork,a approximation algorithm is developed to execute KSRG work and achieve a more efficient and generalized KORS query processing over large-scale query graphs and multi-keywords query requirements.Extensive experiments with real road network datasets demonstrate the effectiveness of our approaches: the proposed algorithms can improve the query efficiency with a limited error rate,meanwhile,can have a feasible query overhead on larger road networks.