Socio-Spatial Group Queries for Impromptu Activity Planning
Authors:
- 14 August 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 28 (1) , 196-210
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 relationships 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. We first consider a special case of MRGQ, namely the Socio-Spatial Group Query (SSGQ), to determine a set of socially acquainted attendees while minimizing the total spatial distance to a specific activity location. We prove that SSGQ is NP-hard and formulate an Integer Linear Programming optimization model for SSGQ. We then develop an efficient algorithm, called SSGS, which employs effective pruning techniques to reduce the running time to determine the optimal solution. Moreover, we propose a heuristic algorithm for SSGQ to efficiently produce good solutions. We next consider the more general MRGQ. 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 SSGS and MAGS over manual coordination in terms of both solution quality and efficiency. Experimental results on real datasets show that our algorithms can process SSGQ and MRGQ efficiently and significantly outperform other baseline algorithms, including one based on the commercial parallel optimizer IBM CPLEX.Keywords
All Related Versions
Funding Information
- Ministry of Science and Technology, Taiwan (103-2221-E-002-286-MY2, MOST 101-2628-E-001-003-MY3, MOST 103-2221-E-001-005-MY2)
This publication has 17 references indexed in Scilit:
- Circle of Friend Query in Geo-Social NetworksLecture Notes in Computer Science, 2012
- On social-temporal group query with acquaintance constraintProceedings of the VLDB Endowment, 2011
- Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar GraphsSIAM Journal on Discrete Mathematics, 2005
- The TPR*-Tree2003
- Indexing the positions of continuously moving objectsACM SIGMOD Record, 2000
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- The $L(2,1)$-Labeling Problem on GraphsSIAM Journal on Discrete Mathematics, 1996
- Nearest neighbor queriesACM SIGMOD Record, 1995
- The R*-tree: an efficient and robust access method for points and rectanglesACM SIGMOD Record, 1990
- Network structure and minimum degreeSocial Networks, 1983