Socio-Spatial Group Queries for Impromptu Activity Planning
Preprint
Abstract
The development and integration of social networking services and smartphones have made it easy for individuals to organize impromptu social activities anywhere and anytime. Main challenges arising in organizing impromptu activities are mostly due to the requirements of making timely invitations in accordance with the potential activity locations, corresponding to the locations of and the relationship among the candidate attendees. Various combinations of candidate attendees and activity locations create a large solution space. Thus, in this paper, we propose Multiple Rally-Point Social Spatial Group Query (MRGQ), to select an appropriate activity location for a group of nearby attendees with tight social relationships. Although MRGQ is NP-hard, the number of attendees in practice is usually small enough such that an optimal solution can be found efficiently. Therefore, we first propose an Integer Linear Programming optimization model for MRGQ. We then design an efficient algorithm, called MAGS, which employs effective search space exploration and pruning strategies to reduce the running time for finding the optimal solution. We also propose to further optimize efficiency by indexing the potential activity locations. A user study demonstrates the strength of using MAGS over manual coordination in terms of both solution quality and efficiency. Experimental results on real datasets show that our algorithms can process MRGQ efficiently and significantly outperform other baseline algorithms, including one based on the commercial parallel optimizer IBM CPLEX.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Circle of Friend Query in Geo-Social NetworksLecture Notes in Computer Science, 2012
- Team Formation for Generalized Tasks in Expertise Social Networks2010
- Finding a team of experts in social networks2009
- Continuous visible nearest neighbor queries2009
- Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar GraphsSIAM Journal on Discrete Mathematics, 2005
- Group nearest neighbor queries2004
- Continuous Nearest Neighbor Search2002
- The $L(2,1)$-Labeling Problem on GraphsSIAM Journal on Discrete Mathematics, 1996
- Network structure and minimum degreeSocial Networks, 1983