We study the problem of extracting a small subset of representative items from a large data stream. Following the convention in many data mining and machine learning applications such as data summarization, recommender systems, and social network analysis, the problem is formulated as maximizing a monotone submodular function subject to a cardinality constraint -- i.e., the size of the selected subset is restricted to be smaller than or equal to an input integer $k$. In this paper, we consider the problem with additional \emph{fairness constraints}, which takes into account the group membership of data items and limits the number of items selected from each group to a given number. We propose efficient algorithms for this fairness-aware variant of the streaming submodular maximization problem. In particular, we first provide a $(\frac{1}{2}-\varepsilon)$-approximation algorithm that requires $O(\frac{1}{\varepsilon} \cdot \log \frac{k}{\varepsilon})$ passes over the stream for any constant $ \varepsilon>0 $. In addition, we design a single-pass streaming algorithm that has the same $(\frac{1}{2}-\varepsilon)$ approximation ratio when unlimited buffer size and post-processing time is permitted.

本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题，并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。

从数据流中公平且代表性地选择子集