On Efficient Processing of Group and Subsequent Queries for Social Activity Planning
On Efficient Processing of Group and Subsequent Queries for Social Activity Planning
复制标题
DOI：
10.1109/tkde.2018.2875911
复制
发表时间：
2019-12
影响因子：
8.9
通讯作者：
Yi-Ling Chen;De-Nian Yang;Chih-Ya Shen;Wang-Chien Lee;Ming-Syan Chen
中科院分区：
文献类型：
--
作者：
Yi-Ling Chen;De-Nian Yang;Chih-Ya Shen;Wang-Chien Lee;Ming-Syan Chen
社会活动计划的三个基本标准很重要：(1)找到熟悉发起人的参与者，(2)确保大多数参与者彼此之间有密切的社会关系，(3)选择一个所有人都可以参加的活动时段。在本文中，我们提出了社会-时态组查询(STGQ)来寻找最小社会总距离的合适的时间和参与者。我们首先证明了该问题是NP难的，并且在任何比率下都是不可逼近的。接下来，我们设计了两种算法，SGSelect和STGSelect，它们包含了有效的剪枝技术，大大减少了运行时间。此外，由于用户可以迭代地调整查询参数来微调结果，我们研究了后续社会组查询(SSGQ)问题。我们提出了累积搜索树和社会边界来缓存和索引先前查询的中间结果，以加速后续查询处理。实验结果表明，SGSelect和STGSelect方法的效率明显高于基线方法。使用缓存机制，后续查询的处理时间可以进一步减少50%-75%。我们进行了一项用户研究，将所提出的方法与人工活动协调进行了比较。结果表明，该方法以较低的协调努力获得了较高质量的解，从而提高了用户组织活动的意愿。
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.