Semantic and influence aware k-representative queries over social streams

• Main Authors: WANG, Yanhao, LI, Yuchen, TAN, Kianlee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Approximation algorithms; Database systems; Semantics; Vector spaces; Information sources; Query results; Query vectors; Real-world datasets; Sliding Window; Social streams; Theoretical guarantees; Topic Modeling; Query processing; Databases and Information Systems; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4371; https://ink.library.smu.edu.sg/context/sis_research/article/5374/viewcontent/Semantic_and_influence_aware_krepresentative_queries_over_social_streams2019.pdf
• Institution: Singapore Management University

Massive volumes of data continuously generated on social platforms have become an important information source for users. A primary method to obtain fresh and valuable information from social streams is social search. Although there have been extensive studies on social search, existing methods only focus on the relevance of query results but ignore the representativeness. In this paper, we propose a novel Semantic and Influence aware k-Representative (k-SIR) query for social streams based on topic modeling. Specifically, we consider that both user queries and elements are represented as vectors in the topic space. A k-SIR query retrieves a set of k elements with the maximum representativeness over the sliding window at query time w.r.t. the query vector. The representativeness of an element set comprises both semantic and influence scores computed by the topic model. Subsequently, we design two approximation algorithms, namely MULTI-TOPIC THRESHOLDSTREAM (MTTS) and MULTI-TOPIC THRESHOLDDESCEND (MTTD), to process k-SIR queries in real-time. Both algorithms leverage the ranked lists maintained on each topic for k-SIR processing with theoretical guarantees. Extensive experiments on real-world datasets demonstrate the effectiveness of k-SIR query compared with existing methods as well as the efficiency and scalability of our proposed algorithms for k-SIR processing.