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 · IEEE Transactions on Services Computing · 2023
Real-timesocial interactions andmulti-streamingare two critical features oflive 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 designSDSSel, 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 proposeTDSSel, a 2-approximation algorithm without any error to SDSQ-T. We propose two pruning strategies,PCPandCDPto 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 designGPDSel, 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.