Group-based collective keyword querying in road networks

This paper addresses a group-based collective keyword (GBCK) query problem in road networks. We model the road network as an undirected graph, where each node locating in a two-dimensional space represents a road intersection or a Points of Interest (POI), and each edge with weight represents a road segment. The GBCK query aims to find a region containing a set of POIs that covers all the query keywords and these POIs are close to the group of users and are close to each other. We show the problem of answering the GBCK query is NP-hard. To solve this problem, we develop a series of query processing algorithms. We first propose an efficient algorithm, which gives a 5-factor approximation to find a feasible region. The cost of this region is further used to limit the search space in the other algorithms. We then propose an exact algorithm, and an approximate algorithm with a 157-factor approximation. Extensive performance studies using real datasets confirm the efficiency and accuracy of the proposed algorithms.