Abstract | ||
---|---|---|
Three essential criteria are important for social activity planning: (1) finding attendees familiar with the initiator, (2) ensuring most attendees have tight social relations with each other, and (3) selecting an activity period available to all. In this paper, we propose the
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Social-Temporal Group Query (STGQ)</italic>
to find suitable time and attendees with minimum total social distance. We first prove that the problem is NP-hard and inapproximable within any ratio. Next, we design two algorithms,
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SGSelect</italic>
and
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">STGSelect</italic>
, which include effective pruning techniques to substantially reduce running time. Moreover, as users may iteratively adjust query parameters to fine tune the results, we study the problem of
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Subsequent Social Group Query (SSGQ)</italic>
. We propose the
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Accumulative Search Tree</italic>
and
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Social Boundary</italic>
, to cache and index intermediate results of previous queries in order to accelerate subsequent query processing. Experimental results indicate that SGSelect and STGSelect are significantly more efficient than baseline approaches. With the caching mechanisms, processing time of subsequent queries can be further reduced by 50-75 percent. We conduct a user study to compare the proposed approach with manual activity coordination. The results show that our approach obtains higher quality solutions with lower coordination effort, thereby increasing the users’ willingness to organize activities. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1109/tkde.2018.2875911 | IEEE Transactions on Knowledge and Data Engineering |
Keywords | Field | DocType |
Indexes,Electronic mail,Social groups,Manuals,Schedules,Social network services | Social group,Social relation,Query string,Computer science,Cache,Social activity,Theoretical computer science,Social distance,Schedule,Artificial intelligence,Machine learning,Search tree | Journal |
Volume | Issue | ISSN |
31 | 12 | 1041-4347 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yi-ling Chen | 1 | 14 | 4.81 |
De-Nian Yang | 2 | 586 | 66.66 |
Chih-Ya Shen | 3 | 103 | 17.13 |
Wang-Chien Lee | 4 | 5765 | 346.32 |
Ming Chen | 5 | 6507 | 1277.71 |