Task-Optimized group search for social internet of things

Chih Ya Shen, Hong-Han Shuai, Kuo Feng Hsu, Ming Syan Chen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


With the maturity and popularity of Internet of Things (IoT), the notion of Social Internet of Things (SIoT) has been proposed to support novel applications and networking services for the IoT in more effective and efficient ways. Although there are many works for SIoT, they focus on designing the architectures and protocols for SIoT under the specific schemes. How to efficiently utilize the collaboration capability of SIoT to complete complex tasks remains unexplored. Therefore, we propose a new query, namely Task-Optimized Group Search (TOGS), to address this need. TOGS aims to extract the target SIoT group such that the target SIoT group will be able to easily communicate with each other while maximizing the accuracy of performing the given tasks. We propose two problem formulations, namely Bounded Communication-loss TOSS (BC-TOSS) and Robustness Guaranteed TOSS (RG-TOSS), for different communication scenarios, and prove that they are both NP-Hard and inapproximable. We propose a polynomial-time algorithm with performance bound for BC-TOSS, and an efficient polynomial-time algorithm to obtain good solutions for RG-TOSS. The experimental results on real datasets indicate that our proposed algorithms outperform other baselines.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2017
Subtitle of host publication20th International Conference on Extending Database Technology, Proceedings
EditorsBernhard Mitschang, Volker Markl, Sebastian Bress, Periklis Andritsos, Kai-Uwe Sattler, Salvatore Orlando
Number of pages3
ISBN (Electronic)9783893180738
StatePublished - 1 Jan 2017
Event20th International Conference on Extending Database Technology, EDBT 2017 - Venice, Italy
Duration: 21 Mar 201724 Mar 2017

Publication series

NameAdvances in Database Technology - EDBT
ISSN (Electronic)2367-2005


Conference20th International Conference on Extending Database Technology, EDBT 2017

Fingerprint Dive into the research topics of 'Task-Optimized group search for social internet of things'. Together they form a unique fingerprint.

Cite this