Publication Type

Journal Article

Version

publishedVersion

Publication Date

7-2018

Abstract

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 KS instances over the sliding window. Theoretically, KW is 1−ε1+d -approximate for SMDK. Furthermore, we propose a KnapWindowPlus framework ( KW+ ) to improve upon KW. KW+ builds an index SubKnapChk to manage the checkpoints. By keeping much fewer checkpoints, KW+ achieves higher efficiency than KW while guaranteeing a 1−ε′2+2d -approximate solution for SMDK. Finally, we evaluate KW and KW+ in real-world datasets. The experimental results demonstrate that KW achieves more than two orders of magnitude speedups over the batch baseline and preserves high-quality solutions for SMDK. KW+ further runs 5-10 times faster than KW while providing solutions with equivalent or better utilities.

Keywords

Approximation algorithm, Approximation algorithms, Data mining, Data models, data stream, Data summarization, Heuristic algorithms, Indexes Kernel, Microsoft Windows, Sliding window, Submodular maximization

Discipline

Databases and Information Systems | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

IEEE Transactions on Knowledge and Data Engineering

First Page

1

Last Page

14

ISSN

1041-4347

Identifier

10.1109/TKDE.2018.2854182

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TKDE.2018.2854182

Download

Share

COinS