Group Nearest Compact POI Set Queries in Road Networks

Identifying a set of points of interest (POIs) is an important problem that finds applications in Location-Based Services (LBS). In this paper, we study a new spatial keyword query motivated by the scenario where a group of users staying at different places wishes to find a compact set of POIs (such as a restaurant and two museums) that is close to all users. We define the problem of group nearest compact POI set (GNCS) query in road networks and show that this problem is NP-hard. To solve the problem, we design query processing algorithms including a first feasible result search algorithm based on the perspective of each individual user, and an exact algorithm with optimizations based on the heuristic of first minimizing the aggregate distance between the POI set and the user group. Extensive performance studies using two real datasets confirm the efficiency and accuracy of our proposed algorithms.