Submodular maximization (SM) has become a silver bullet for a broad class of applications such as influence maximization, data summarization, top-$k$ representative queries, and recommendations. In this paper, we study the SM problem in data streams. Most existing algorithms for streaming SM only support the append-only model with cardinality constraints, which cannot meet the requirements of real-world problems considering either the data recency issues or more general $d$-knapsack constraints. Therefore, we first propose an append-only streaming algorithm {\sc KnapStream} for SM subject to a $d$-knapsack constraint (SMDK). Furthermore, we devise the {\sc KnapWindow} algorithm for SMDK over sliding windows to capture the recency constraints. Theoretically, the proposed algorithms have constant approximation ratios for a fixed number of knapsacks and sublinear complexities. We finally evaluate the efficiency and effectiveness of our algorithms in two real-world datasets. The results show that the proposed algorithms achieve two orders of magnitude speedups over the greedy baseline in the batch setting while preserving high quality solutions.

提出了一种在数据流上优化代表性子集选择的动态RSS方法，即最大化子模函数在具有一般 d-背包约束(SMDK)的滑动窗口上。KnapWindow框架（KW）利用KnapStream算法（KS）为SMDK策略中的“添加仅”数据流实例，提出KnapWindowPlus框架（KW$^{+}$）来改进KW。实验结果表明，KW和KW$^{+}$在保持SMDK高质量解的同时，比批处理基线减少了两个数量级以上的运行时间。

滑动窗口上高效的代表子集选择