We study the problem of extracting a small subset of representative items
from a large data stream. In many data mining and machine learning applications
such as social network analysis and recommender systems, this problem can be
formulated as maximizing a monotone submodular function subject to a
cardinality constraint $k$. In this work, we consider the setting where data
items in the stream belong to one of several disjoint groups and investigate
the optimization problem with an additional \emph{fairness} constraint that
limits selection to a given number of items from each group. We then propose
efficient algorithms for the fairness-aware variant of the streaming submodular
maximization problem. In particular, we first give a $
(\frac{1}{2}-\varepsilon) $-approximation algorithm that requires $
O(\frac{1}{\varepsilon} \log \frac{k}{\varepsilon}) $ passes over the stream
for any constant $ \varepsilon>0 $. Moreover, we give a single-pass streaming
algorithm that has the same approximation ratio of $(\frac{1}{2}-\varepsilon)$
when unlimited buffer sizes and post-processing time are permitted, and discuss
how to adapt it to more practical settings where the buffer sizes are bounded.
Finally, we demonstrate the efficiency and effectiveness of our proposed
algorithms on two real-world applications, namely \emph{maximum coverage on
large graphs} and \emph{personalized recommendation}.

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