Group-based keyword-aware route querying in road networks

This paper addresses a group-based keyword-aware route (GKAR) query problem in road networks. The road network with Points of Interest (POIs) is modeled as an undirected graph, where each node with coordinates represents a road intersection or a POI, and each weighted edge represents a road segment. The GAKR query aims to find a POI route such that it passes by a set of required keywords sequentially, and the cost of the route is minimized. The GKAR query problem is NP-hard. To solve this problem, we develop a series of query processing algorithms. We first propose two efficient algorithms which give an (n+3)-factor approximation and an (n+1)-factor approximation respectively to find a feasible POI route, where n represents the number of query keywords. The cost of this result is further used to limit the search space in the following algorithms. We then present two exact algorithms, and one greedy algorithm. The first exact algorithm finds the optimal result by enumerating all feasible POI routes. To improve the efficiency, we propose another exact algorithm based on the property of the cost function. At last, we propose a greedy algorithm to make comparisons. Extensive experiments with two real datasets confirm the efficiency, accuracy, and scalability of our proposed algorithms.