TY - GEN

T1 - Submodular Optimization over Streams with Inhomogeneous Decays

AU - Zhao, Junzhou

AU - Shang, Shuo

AU - Wang, Pinghui

AU - Lui, John C. S.

AU - Zhang, Xiangliang

N1 - KAUST Repository Item: Exported on 2021-08-31
Acknowledgements: We would like to thank the anonymous reviewers for their valuable comments and suggestions to help us improve this
paper. This work is financially supported by the King Abdullah University of Science and Technology (KAUST) Sensor
Initiative, Saudi Arabia. The work of John C.S. Lui was supported in part by the GRF Funding 14208816.

PY - 2019

Y1 - 2019

N2 - Cardinality constrained submodular function maximization, which aims to select a subset of size at most k to maximize a monotone submodular utility function, is the key in many data mining and machine learning applications such as data summarization and maximum coverage problems. When data is given as a stream, streaming submodular optimization (SSO) techniques are desired. Existing SSO techniques can only apply to insertion-only streams where each element has an infinite lifespan, and sliding-window streams where each element has a same lifespan (i.e., window size). However, elements in some data streams may have arbitrary different lifespans, and this requires addressing SSO over streams with inhomogeneous-decays (SSO-ID). This work formulates the SSO-ID problem and presents three algorithms: BASIC-STREAMING is a basic streaming algorithm that achieves an (1/2 − ɛ) approximation factor; HISTAPPROX improves the efficiency significantly and achieves an (1/3 − ɛ) approximation factor; HISTSTREAMING is a streaming version of HISTAPPROX and uses heuristics to further improve the efficiency. Experiments conducted on real data demonstrate that HISTSTREAMING can find high quality solutions and is up to two orders of magnitude faster than the naive GREEDY algorithm.

AB - Cardinality constrained submodular function maximization, which aims to select a subset of size at most k to maximize a monotone submodular utility function, is the key in many data mining and machine learning applications such as data summarization and maximum coverage problems. When data is given as a stream, streaming submodular optimization (SSO) techniques are desired. Existing SSO techniques can only apply to insertion-only streams where each element has an infinite lifespan, and sliding-window streams where each element has a same lifespan (i.e., window size). However, elements in some data streams may have arbitrary different lifespans, and this requires addressing SSO over streams with inhomogeneous-decays (SSO-ID). This work formulates the SSO-ID problem and presents three algorithms: BASIC-STREAMING is a basic streaming algorithm that achieves an (1/2 − ɛ) approximation factor; HISTAPPROX improves the efficiency significantly and achieves an (1/3 − ɛ) approximation factor; HISTSTREAMING is a streaming version of HISTAPPROX and uses heuristics to further improve the efficiency. Experiments conducted on real data demonstrate that HISTSTREAMING can find high quality solutions and is up to two orders of magnitude faster than the naive GREEDY algorithm.

UR - http://hdl.handle.net/10754/670838

UR - https://aimagazine.org/ojs/index.php/AAAI/article/view/4535

U2 - 10.1609/aaai.v33i01.33015861

DO - 10.1609/aaai.v33i01.33015861

M3 - Conference contribution

SP - 5861

EP - 5868

BT - Proceedings of the AAAI Conference on Artificial Intelligence

PB - Association for the Advancement of Artificial Intelligence (AAAI)

ER -