Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
Efficient Representative Subset Selection Over Sliding Windows, Yanhao Wang, Yuchen Li, Kian-Lee Tan
Efficient Representative Subset Selection Over Sliding Windows, Yanhao Wang, Yuchen Li, Kian-Lee Tan
Research Collection School Of Computing and Information Systems
Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as submodular maximization to capture the "diminishing returns" property of representativeness, but often only has a single constraint, which limits its applications to many real-world problems. To capture the recency issue and support various constraints, we formulate dynamic RSS as maximizing submodular functions subject to general d -knapsack constraints (SMDK) over sliding windows. We propose a KnapWindow framework (KW) for SMDK. KW utilizes KnapStream (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and …
A Sliding-Window Framework For Representative Subset Selection, Yanhao Wang, Yuchen Li, Kian-Lee Tan
A Sliding-Window Framework For Representative Subset Selection, Yanhao Wang, Yuchen Li, Kian-Lee Tan
Research Collection School Of Computing and Information Systems
Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. A common approach is to model RSS as the submodular maximization problem because the utility of extracted representatives often satisfies the "diminishing returns" property. To capture the data recency issue and support different types of constraints in real-world problems, we formulate RSS as maximizing a submodular function subject to a d-knapsack constraint (SMDK) over sliding windows. Then, we propose a novel KnapWindow framework for SMDK. Theoretically, KnapWindow is 1-ε/1+d - approximate for SMDK and achieves sublinear complexity. Finally, we evaluate the efficiency and effectiveness …
Location-Aware Influence Maximization Over Dynamic Social Streams, Yanhao Wang, Yuchen Li, Ju Fan, Kianlee Tan
Location-Aware Influence Maximization Over Dynamic Social Streams, Yanhao Wang, Yuchen Li, Ju Fan, Kianlee Tan
Research Collection School Of Computing and Information Systems
Influence maximization (IM), which selects a set of k seed users (a.k.a., a seed set) to maximize the influence spread over a social network, is a fundamental problem in a wide range of applications. However, most existing IM algorithms are static and location-unaware. They fail to provide high-quality seed sets efficiently when the social network evolves rapidly and IM queries are location-aware. In this article, we first define two IM queries, namely Stream Influence Maximization (SIM) and Location-aware SIM (LSIM), to track influential users over social streams. Technically, SIM adopts the sliding window model and maintains a seed set with …