@inproceedings{ca0bd02312ac41908603c26b5413efc2,
title = "A sliding-window framework for representative subset selection",
abstract = "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.",
keywords = "Approximation algorithm, Data stream, Data summarization, Sliding window, submodular maximization",
author = "Yanhao Wang and Yuchen Li and Tan, \{Kian Lee\}",
note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 34th IEEE International Conference on Data Engineering, ICDE 2018 ; Conference date: 16-04-2018 Through 19-04-2018",
year = "2018",
month = oct,
day = "24",
doi = "10.1109/ICDE.2018.00127",
language = "英语",
series = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1272--1275",
booktitle = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
address = "美国",
}