Submodular maximization over data streams with differential privacy noise
Journal article
Guo, Longkun, Liao, Kewen, Xiao, Di and Yao, Pei. (2023). Submodular maximization over data streams with differential privacy noise. Theoretical Computer Science. 944, p. Article 113625. https://doi.org/10.1016/j.tcs.2022.11.011
Authors | Guo, Longkun, Liao, Kewen, Xiao, Di and Yao, Pei |
---|---|
Abstract | In the big data era, data often comes in the form of streams and fast data stream analysis has recently attracted intensive research interest. Submodular optimization naturally appears in many streaming data applications such as social network influence maximization with the property of diminishing returns. However, in a practical setting, streaming data frequently comes with noises that are small but significant enough to impact the optimality of submodular optimization solutions. Following the framework of differential privacy (DP), this paper considers a streaming model with DP noise that is small by construction. Within this noisy streaming model, the paper strives to address the general problem of submodular maximization with a cardinality constraint. The main theoretical result we obtained is a streaming algorithm that is one-pass and has an approximation guarantee of [*] for any [*]. Finally, we implement the algorithm and evaluate it against several baseline methods. Numerical results support the practical performance of our algorithm across several real datasets. [*] See publisher's abstract for mathematics: https://doi.org/10.1016/j.tcs.2022.11.011 |
Keywords | submodular maximization; streaming algorithm; differential privacy noise |
Year | 2023 |
Journal | Theoretical Computer Science |
Journal citation | 944, p. Article 113625 |
Publisher | Elsevier B.V. |
ISSN | 0304-3975 |
Digital Object Identifier (DOI) | https://doi.org/10.1016/j.tcs.2022.11.011 |
Scopus EID | 2-s2.0-85146427060 |
Page range | 1-12 |
Funder | National Natural Science Foundation of China (NSFC) |
Science and Technology Support Plan for Youth Innovation of Colleges and Universities of Shandong Province of China | |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
Online | 15 Dec 2022 |
Publication process dates | |
Accepted | 11 Nov 2022 |
Deposited | 21 Jun 2023 |
Grant ID | 12271098 |
61772005 | |
2020KJN008 |
https://acuresearchbank.acu.edu.au/item/8z29z/submodular-maximization-over-data-streams-with-differential-privacy-noise
Restricted files
Publisher's version
93
total views0
total downloads2
views this month0
downloads this month