Streaming fair submodular maximization is attracting considerable research interest due to its broad applications in machine learning, particularly for tasks such as feature selection and text summary against large-scale data and fairness considerations. Given a sequence of data points belonging to distinct groups and arriving in a streaming manner, the problem aims to select k data points from the stream to maximize the total revenue of the selected points. In this paper, we first devise an efficient \((\frac{1}{2}-\varepsilon )\) -approximation algorithm with \(O(\log (\frac{1}{\varepsilon }\log \frac{k}{\varepsilon }))\) passes, an improvement over the previous \(O(\frac{1}{\varepsilon }\log \frac{k}{\varepsilon })\) passes. Then, we present a \(\left( \frac{1}{3} - \varepsilon \right) \) -approximation algorithm that needs only one pass and consumes a buffer of size \(O(k+|B|)\) and achieves a ratio strictly greater than \(\frac{1}{4}\) while using a buffer of size \(O(k\log k)\) . Lastly, we conduct extensive experiments using real-world datasets to validate our method, demonstrating that it outperforms all state-of-the-art algorithms in terms of efficiency, effectiveness, and scalability.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fair Maximization of Monotone Submodular Functions in Data Streams

  • Shuqian Zhu,
  • Longkun Guo,
  • Jiawei Lin

摘要

Streaming fair submodular maximization is attracting considerable research interest due to its broad applications in machine learning, particularly for tasks such as feature selection and text summary against large-scale data and fairness considerations. Given a sequence of data points belonging to distinct groups and arriving in a streaming manner, the problem aims to select k data points from the stream to maximize the total revenue of the selected points. In this paper, we first devise an efficient \((\frac{1}{2}-\varepsilon )\) -approximation algorithm with \(O(\log (\frac{1}{\varepsilon }\log \frac{k}{\varepsilon }))\) passes, an improvement over the previous \(O(\frac{1}{\varepsilon }\log \frac{k}{\varepsilon })\) passes. Then, we present a \(\left( \frac{1}{3} - \varepsilon \right) \) -approximation algorithm that needs only one pass and consumes a buffer of size \(O(k+|B|)\) and achieves a ratio strictly greater than \(\frac{1}{4}\) while using a buffer of size \(O(k\log k)\) . Lastly, we conduct extensive experiments using real-world datasets to validate our method, demonstrating that it outperforms all state-of-the-art algorithms in terms of efficiency, effectiveness, and scalability.