Group Trip Planning Queries in Spatial Databases

Location-based social networks grow at a remarkable pace. Current location-aware mobile devices enable us to access these networks from anywhere and to connect to friends via social networks in a seamless manner. These networks allow people to interact with friends and colleagues in a novel way, for example, they may want to spontaneously meet in the next hour for dinner at a restaurant nearby followed by a joint visit to a movie theater. This motivates a new query type, which we call a group trip planning (GTP) query: the group has an interest to minimize the total travel distance for all members, and this distance is the sum of each user’s travel distance from each user’s start location to destination via the restaurant and the movie theater. Formally, for a set of user source-destination pairs in a group and different types of data points (e.g., a movie theater versus a restaurant), a GTP query returns for each type of data points those locations that minimize the total travel distance for the entire group. We develop efficient algorithms to answer GTP queries, which we show in extensive experiments.