On Efficient Processing of Queries for Live Multi-Streaming Soiree Organization

C. P. Kankeu Fotsing, Chih Ya Shen, Liang Hao Huang, Yi Shin Chen, Wang Chien Lee, De Nian Yang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Real-time social interactions and multi-streaming are two critical features of live streaming services. In this paper, we formulate a new fundamental service query, Social-aware Diverse and Preferred Organization Query (SDSQ), that jointly selects a set of diverse and preferred live streaming channels and a group of socially tight viewers for organization of a live multi-streaming soiree. We prove that SDSQ is NP-hard and inapproximable within any factor, and design SDSSel, a 2-approximation algorithm with a guaranteed error bound. Moreover, we study SDSQ-T, a special case of SDSQ, where the social graph is a threshold graph, and propose TDSSel, a 2-approximation algorithm without any error to SDSQ-T. We propose two pruning strategies, PCP and CDP to boost SDSSel and TDSSel. We further propose a more challenging but practical service query, Generalized Social-aware Maximum Preferred and Diverse Query (GSPQ), a generalization of SDSQ. We design GPDSel, a 4-approximation algorithm for GSPQ with a guaranteed error bound. We propose a strategy to improve the approximation ratios of the proposed algorithms. A user study on Twitch validates SDSQ, and the large-scale experiments on real datasets demonstrate the superiority of the proposed algorithms over several baselines for live-streaming services.

Original languageEnglish (US)
Pages (from-to)2812-2826
Number of pages15
JournalIEEE Transactions on Services Computing
Issue number4
StatePublished - Jul 1 2023

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications
  • Information Systems and Management

Cite this