On Efficient Processing of Group and Subsequent Queries for Social Activity Planning

Yi Ling Chen, De Nian Yang, Chih Ya Shen, Wang Chien Lee, Ming Syan Chen

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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 Social-Temporal Group Query (STGQ) 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, SGSelect and STGSelect, 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 Subsequent Social Group Query (SSGQ). We propose the Accumulative Search Tree and Social Boundary, 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.

Original languageEnglish (US)
Article number8493329
Pages (from-to)2364-2378
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number12
StatePublished - Dec 1 2019

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'On Efficient Processing of Group and Subsequent Queries for Social Activity Planning'. Together they form a unique fingerprint.

Cite this