A sliding-window framework for representative subset selection

• Main Authors: WANG, Yanhao, LI, Yuchen, TAN, Kian-Lee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Data summarization; submodular maximization; data stream; sliding window; approximation algorithm; Databases and Information Systems; Numerical Analysis and Scientific Computing; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/7123; https://ink.library.smu.edu.sg/context/sis_research/article/8126/viewcontent/552000b268.pdf
• Institution: Singapore Management University

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 of KnapWindow on real-world datasets. The results show that it achieves up to 120x speedups over the batch baseline with at least 94% utility assurance.