Indexed by:
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 [Formula presented] for any δ>0. 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. © 2022
Keyword:
Reprint 's Address:
Email:
Source :
Theoretical Computer Science
ISSN: 0304-3975
Year: 2023
Volume: 944
0 . 9
JCR@2023
0 . 9 0 0
JCR@2023
ESI HC Threshold:32
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 3
Affiliated Colleges: