Abstract
Extracting representative elements from a large stream of data is an important and interesting problem. Such problem can be formulated as maximizing a normalized monotone non-submodular set function subject to a cardinality constraint. In this paper, we first present an algorithm called Non-SubModular-Sieve-Streaming\(^{++}\) for solving this problem by utilizing the concept of diminishing-return ratio, which requires only one pass over the data and obtain tight approximation ratio and minimum memory complexity. Then, for reducing the number of adaptive complexity, we propose an algorithm called Non-SubModular-Batch-Sieve-Streaming\(^{++}\) by buffering a small fraction of the stream and applying a filtering procedure. We analyze the approximation ratios of the two algorithms, which generalize the results of Sieve-Streaming\(^{++}\) and Batch-Sieve-Streaming\(^{++}\) to the non-submodular case. Finally, we illustrate the feasibility and effectiveness of the two algorithms through a numerical example and compare the corresponding results with the existing algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ajtai, M., Jayram, T.S., Kumar, R., Sivakumar, D.: Approximate counting of inversions in a data stream. In: Proceedings of STOC, pp. 370–379 (2002)
Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of SIGKDD, pp. 671–680 (2014)
Badanidiyuru, A., Vondrk, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of SODA, pp. 1497–1514 (2014)
Balkanski, E., Rubinstein, A., Singer, Y.: An exponential speedup in parallel running time for submodular maximization without loss in approximation. In: Proceedings of SODA, pp. 283–302 (2019)
Breuer, A., Balkanski, E., Singer, Y.: The FAST algorithm for submodular maximization. arXiv: 1907.06173 (2019)
Buchbinder, N., Feldman, M., Schwartz, R.: Online submodular maximization with preemption. In: Proceedings of SODA, pp. 1202–1216 (2015)
Buchbinder, N., Feldman, M., Garg, M.: Deterministic \((\frac{1}{2})+\epsilon \)-approximation for submodular maximization over a matroid. In: Proceedings of SODA, pp. 241–254 (2019)
Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: matchings, matroids, and more. Math. Program. 154, 225–247 (2015). https://doi.org/10.1007/s10107-015-0900-7
Chan, T., Huang, Z., Jiang, S., Kang, N., Tang, Z.: Online submodular maximization with free disposal: Randomization beats 0.25 for partition matroids. (2016)
Chekuri, C., Gupta, S., Quanrud, K.: Streaming algorithms for submodular function maximization. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 318–330. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47672-7_26
Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of ICML, pp. 1057–1064 (2011)
Du, D., Li, Y., Xiu, N., Xu, D.: Simultaneous approximation of multi-criteria submodular function maximization. J. Oper. Res. Soc. China 2, 271–290 (2014). https://doi.org/10.1007/s40305-014-0053-z
Dueck, D., Frey, B.J.: Non-metricaffinity propagation for unsupervised image categorization. In: Proceedings of ICCV, pp. 1–8 (2007)
El-Arini, K., Guestrin, C.: Beyond keyword search: discovering relevant scientific literature. In: Proceedings of SIGKDD, pp. 439–447 (2011)
Ene, A., Nguyen, H.: A nearly-linear time algorithm for submodular maximization with a knapsack constraint. In: Proceedings of ICALP, pp. 53:1–53:12 (2019)
El-Arini, K., Veda, G., Shahaf, D., Guestrin, C.: Turning down the noise in the blogosphere. In: Proceedings of SIGKDD, pp. 289–298 (2009)
Elenberg, E., Dimakis, A.G., Feldman, M., Karbasi, A.: Streaming weak submodularity: interpreting neural networks on the fly. In: Proceedings of NIPS, pp. 4044–4054 (2017)
Feige, U.: A threshold of \(\ln n\) for approximating set cover. J. ACM 45, 634–652 (1998)
Feldman, M., Karbasi, A., Kazemi, E.: Do less, get more: streaming submodular maximization with subsampling. In: Proceedings of ANIPS, pp. 730–740 (2018)
Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43, 514–542 (2014)
Goldengorin, B., Ghosh, D.: A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem. J. Glob. Optim. 32, 65–82 (2005). https://doi.org/10.1007/s10898-004-5909-z
Gomes, R., Krause, A.: Budgeted nonparametric learning from data streams. In: Proceedings of ICML, pp. 391–398 (2010)
Guha, S., Mishra, N., Motwani, R., Ocallaghan, L.: Clustering data streams. In: Proceedings of FOCS, pp. 359–366 (2000)
Kazemi, E., Mitrovic, M., Zadimoghaddam, M., Lattanzi, S., Karbasi A.: Submodular streaming in all its glory: tight approximation, minimum memory and low adaptive complexity. In: Proceedings of ICML, pp. 3311–3320 (2019)
Krause, A., Golovin, D.: Submodular function maximization. In: Tractability: Practical Approaches to Hard Problems, pp. 71–104. Cambridge University Press, Cambridge (2014)
Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235–284 (2008)
Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math. Oper. Res. 38, 729–739 (2013)
Lawrence, N., Seeger, M., Herbrich, R.: Fast sparse Gaussian process methods: the informative vector machine. In: Proceedings of NIPS, pp. 625–632 (2003)
Mirzasoleiman, B., Jegelka, S., Krause, A.: Streaming non-monotone sub-modular maximization: personalized video summarization on the fly. arXiv: 1706.03583 (2018)
Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci. 1, 117–236 (2005)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: Ananalysis of approximations for maximizing submodular set functions-I. Math. Program. 14, 265–294 (1978)
Norouzi-Fard, A., Tarnawski J., Mitrovic, S., Zandieh, A., Mousavifar, A., Svensson, O.: Beyond 1/2-approximation for submodular maximization on massive data streams. In: Proceedings of ICML, pp. 3826–3835 (2018)
Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32, 41–43 (2004)
Vondrk, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of STOC, pp. 67–74 (2008)
Wang, Y., Xu, D., Wang, Y., Zhang, D.: Non-submodular maximization on massive data streams. J. Glob. Optim. 76(4), 729–743 (2019). https://doi.org/10.1007/s10898-019-00840-8
Zoubin, G.: Scaling the Indian buffet process via submodular maximization. In: Proceedings of ICML, pp. 1013–1021 (2013)
Acknowledgements
The first author is supported by Natural Science Foundation of China (Nos. 11401438, 11571120). The third author is supported by Natural Science Foundation of Shandong Province (Nos. ZR2017LA002, ZR2019MA022) of China.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Li, M., Zhou, X., Tan, J., Wang, W. (2020). Non-Submodular Streaming Maximization with Minimum Memory and Low Adaptive Complexity. In: Zhang, Z., Li, W., Du, DZ. (eds) Algorithmic Aspects in Information and Management. AAIM 2020. Lecture Notes in Computer Science(), vol 12290. Springer, Cham. https://doi.org/10.1007/978-3-030-57602-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-57602-8_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57601-1
Online ISBN: 978-3-030-57602-8
eBook Packages: Computer ScienceComputer Science (R0)