{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:56Z","timestamp":1750309556860,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":74,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T00:00:00Z","timestamp":1745280000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Natural Science Foundation of China","award":["62172384, 62402410, U22B2060"],"award-info":[{"award-number":["62172384, 62402410, U22B2060"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,4,28]]},"DOI":"10.1145\/3696410.3714890","type":"proceedings-article","created":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T22:57:28Z","timestamp":1745362648000},"page":"4710-4721","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Linear-Time Algorithms for Representative Subset Selection From Data Streams"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6080-4850","authenticated-orcid":false,"given":"Shuang","family":"Cui","sequence":"first","affiliation":[{"name":"Soochow University, Suzhou, Jiangsu, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6302-5366","authenticated-orcid":false,"given":"Kai","family":"Han","sequence":"additional","affiliation":[{"name":"Soochow University, Suzhou, Jiangsu, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0785-707X","authenticated-orcid":false,"given":"Jing","family":"Tang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong, China and The Hong Kong University of Science and Technology, Kowloon, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2025,4,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Conference on Neural Information Processing Systems (NeurIPS).","author":"Amanatidis Georgios","year":"2020","unstructured":"Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenh\u00e4user. 2020. Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13472"},{"key":"e_1_3_2_1_3_1","volume-title":"International Conference on Machine Learning (ICML). 231--242","author":"Amanatidis Georgios","year":"2021","unstructured":"Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, Alberto Marchetti Spaccamela, and Rebecca Reiffenh\u00e4user. 2021. Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity. In International Conference on Machine Learning (ICML). 231--242."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2021.3125147"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330911"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"key":"e_1_3_2_1_8_1","volume-title":"Conference on Neural Information Processing Systems (NeurIPS). 2359--2370","author":"Balkanski Eric","year":"2018","unstructured":"Eric Balkanski, Adam Breuer, and Yaron Singer. 2018. Non-monotone submodular maximization in exponentially fewer iterations. In Conference on Neural Information Processing Systems (NeurIPS). 2359--2370."},{"key":"e_1_3_2_1_9_1","volume-title":"Submodular Maximization in Exactly n Queries. arXiv preprint arXiv:2406.00148","author":"Balkanski Eric","year":"2024","unstructured":"Eric Balkanski, Steven DiSilvio, and Alan Kuhnle. 2024. Submodular Maximization in Exactly n Queries. arXiv preprint arXiv:2406.00148 (2024)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Wei-Xuan Bao Jun-Yi Hang and Min-Ling Zhang. 2022. Submodular feature selection for partial label learning. In ACM Knowledge Discovery and Data Mining (SIGKDD). 26--34.","DOI":"10.1145\/3534678.3539292"},{"key":"e_1_3_2_1_11_1","volume-title":"Testing submodularity and other properties of valuation functions. arXiv preprint arXiv:1611.07879","author":"Blais Eric","year":"2016","unstructured":"Eric Blais and Abhinav Bommireddi. 2016. Testing submodularity and other properties of valuation functions. arXiv preprint arXiv:1611.07879 (2016)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0900-7"},{"key":"e_1_3_2_1_14_1","volume-title":"International Joint Conference on Natural Language Processing (IJCNLP). 418--424","author":"Chali Yllias","year":"2017","unstructured":"Yllias Chali, Moin Tanvee, and Mir Tafseer Nayeem. 2017. Towards abstractive multi-document summarization using submodular function-based framework, sentence compression and merging. In International Joint Conference on Natural Language Processing (IJCNLP). 418--424."},{"key":"e_1_3_2_1_15_1","volume-title":"Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel. In Conference on Neural Information Processing Systems (NeurIPS)","volume":"34","author":"Chen Yixin","year":"2021","unstructured":"Yixin Chen, Tonmoy Dey, and Alan Kuhnle. 2021. Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel. In Conference on Neural Information Processing Systems (NeurIPS), Vol. 34."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Yixin Chen and Alan Kuhnle. 2023. Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 250--261.","DOI":"10.1145\/3580305.3599259"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583490"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Shuang Cui Kai Han Shaojie Tang Feng Li and Jun Luo. 2024. Fairness in Streaming Submodular Maximization Subject to a Knapsack Constraint. In ACM Knowledge Discovery and Data Mining (SIGKDD). 514--525.","DOI":"10.1145\/3637528.3671778"},{"key":"e_1_3_2_1_19_1","volume-title":"International Conference on Machine Learning (ICML). 2222--2232","author":"Cui Shuang","year":"2021","unstructured":"Shuang Cui, Kai Han, Tianshuai Zhu, Jing Tang, Benwei Wu, and He Huang. 2021. Randomized Algorithms for Submodular Function Maximization with a k -System Constraint. In International Conference on Machine Learning (ICML). 2222--2232."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"e_1_3_2_1_21_1","volume-title":"International Conference on Machine Learning (ICML). 5671--5693","author":"D\u00fctting Paul","year":"2022","unstructured":"Paul D\u00fctting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. 2022. Deletion robust submodular maximization over matroids. In International Conference on Machine Learning (ICML). 5671--5693."},{"key":"e_1_3_2_1_22_1","volume-title":"International Conference on Machine Learning (ICML). 8821--8835","author":"D\u00fctting Paul","year":"2023","unstructured":"Paul D\u00fctting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. 2023. Fully dynamic submodular maximization over matroids. In International Conference on Machine Learning (ICML). 8821--8835."},{"key":"e_1_3_2_1_23_1","volume-title":"International Conference on Machine Learning (ICML). 9150--9171","author":"Halabi Marwa El","year":"2023","unstructured":"Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub Tarnawski. 2023. Fairness in streaming submodular maximization over a matroid constraint. In International Conference on Machine Learning (ICML). 9150--9171."},{"key":"e_1_3_2_1_24_1","volume-title":"Conference on Neural Information Processing Systems (NeurIPS).","author":"Halabi Marwa El","year":"2020","unstructured":"Marwa El Halabi, Slobodan Mitrovi\u0107, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub M Tarnawski. 2020. Fairness in streaming submodular maximization: Algorithms and hardness. In Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_25_1","first-page":"53","article-title":"A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint","volume":"132","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Huy L Nguyen. 2019a. A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. In International Colloquium on Automata, Languages and Programming (ICALP), Vol. 132. 53.","journal-title":"International Colloquium on Automata, Languages and Programming (ICALP)"},{"key":"e_1_3_2_1_26_1","volume-title":"Languages and Programming (ICALP)","volume":"132","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Huy L Nguyen. 2019b. Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint. In International Colloquium on Automata, Languages and Programming (ICALP), Vol. 132."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316389"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052699"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2011.10.002"},{"key":"e_1_3_2_1_30_1","volume-title":"International Conference on Machine Learning (ICML). 1833--1842","author":"Fahrbach Matthew","year":"2019","unstructured":"Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. 2019. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In International Conference on Machine Learning (ICML). 1833--1842."},{"key":"e_1_3_2_1_31_1","first-page":"72","article-title":"How do you want your greedy: Simultaneous or repeated","volume":"24","author":"Feldman Moran","year":"2023","unstructured":"Moran Feldman, Christopher Harshaw, and Amin Karbasi. 2023. How do you want your greedy: Simultaneous or repeated? Journal of Machine Learning Research (JMLR), Vol. 24 (2023), 72--1.","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0373-y"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743493"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17572-5_20"},{"key":"e_1_3_2_1_36_1","volume-title":"Conference on Neural Information Processing Systems (NeurIPS).","author":"Han Kai","year":"2020","unstructured":"Kai Han, Zongmai Cao, Shuang Cui, and Benwei Wu. 2020. Deterministic approximation for submodular maximization over a matroid in nearly linear time. In Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410220.3453922"},{"key":"e_1_3_2_1_38_1","volume-title":"International Conference on Machine Learning (ICML). 2634--2643","author":"Harshaw Chris","year":"2019","unstructured":"Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. 2019. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In International Conference on Machine Learning (ICML). 2634--2643."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367524"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00786-4"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-021-10065-6"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00628-y"},{"key":"e_1_3_2_1_43_1","volume-title":"Randomized Pricing with Deferred Acceptance for Revenue Maximization with Submodular Objectives. In International World Wide Web Conferences (WWW). 3530--3540","author":"Huang He","year":"2023","unstructured":"He Huang, Kai Han, Shuang Cui, and Jing Tang. 2023. Randomized Pricing with Deferred Acceptance for Revenue Maximization with Submodular Objectives. In International World Wide Web Conferences (WWW). 3530--3540."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3123944"},{"key":"e_1_3_2_1_45_1","volume-title":"International Conference on Machine Learning (ICML). 5356--5366","author":"Kazemi Ehsan","year":"2021","unstructured":"Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. 2021. Regularized submodular maximization at scale. In International Conference on Machine Learning (ICML). 5356--5366."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_3_2_1_48_1","volume-title":"International conference on machine learning (ICML). 1301--1309","author":"Korda Nathan","year":"2016","unstructured":"Nathan Korda, Balazs Szorenyi, and Shuai Li. 2016. Distributed clustering of linear bandits in peer to peer networks. In International conference on machine learning (ICML). 1301--1309."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(516)"},{"key":"e_1_3_2_1_50_1","volume-title":"Conference on Neural Information Processing Systems (NeurIPS)","volume":"32","author":"Kuhnle Alan","year":"2019","unstructured":"Alan Kuhnle. 2019. Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. In Conference on Neural Information Processing Systems (NeurIPS), Vol. 32."},{"key":"e_1_3_2_1_51_1","unstructured":"Alan Kuhnle. 2021. Quick streaming algorithms for maximization of monotone submodular functions in linear time. In Artificial Intelligence and Statistics (AISTATS). 1360--1368."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/2481023"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0592"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536459"},{"key":"e_1_3_2_1_55_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. https:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-012-0336-1"},{"key":"e_1_3_2_1_57_1","volume-title":"Conference on Neural Information Processing Systems (NeurIPS)","volume":"35","author":"Li Wenxin","year":"2022","unstructured":"Wenxin Li, Moran Feldman, Ehsan Kazemi, and Amin Karbasi. 2022. Submodular maximization in clean linear time. In Conference on Neural Information Processing Systems (NeurIPS), Vol. 35. 17473--17487."},{"key":"e_1_3_2_1_58_1","volume-title":"Annual Meeting of the Association for Computational Linguistics (ACL). 510--520","author":"Lin Hui","year":"2011","unstructured":"Hui Lin and Jeff Bilmes. 2011. A class of submodular functions for document summarization. In Annual Meeting of the Association for Computational Linguistics (ACL). 510--520."},{"key":"e_1_3_2_1_59_1","volume-title":"Conference on Uncertainty in Artificial Intelligence (UAI). 479--490","author":"Lin Hui","year":"2012","unstructured":"Hui Lin and Jeff Bilmes. 2012. Learning mixtures of submodular shells with application to document summarization. In Conference on Uncertainty in Artificial Intelligence (UAI). 479--490."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3392717.3392748"},{"key":"e_1_3_2_1_61_1","volume-title":"International Conference on Machine Learning (ICML). 1358--1367","author":"Mirzasoleiman Baharan","year":"2016","unstructured":"Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning (ICML). 1358--1367."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467367"},{"volume-title":"International Joint Conference on Artificial Intelligence (IJCAI). 4127--4135","author":"Pham Canh V.","key":"e_1_3_2_1_64_1","unstructured":"Canh V. Pham, Tan D. Tran, Dung T. K. Ha, and My T. Thai. 2023. Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint. In International Joint Conference on Artificial Intelligence (IJCAI). 4127--4135."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.60"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9719-2"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380275"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447386"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449799"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.3.410"},{"key":"e_1_3_2_1_72_1","volume-title":"International Conference on Artificial Intelligence and Statistics (AISTATS). 3263--3274","author":"Yaroslavtsev Grigory","year":"2020","unstructured":"Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. 2020. ''bring your own greedy'' max: Near-optimal 1\/2-approximations for submodular knapsack. In International Conference on Artificial Intelligence and Statistics (AISTATS). 3263--3274."},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.10146"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM54844.2022.00078"}],"event":{"name":"WWW '25: The ACM Web Conference 2025","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"],"location":"Sydney NSW Australia","acronym":"WWW '25"},"container-title":["Proceedings of the ACM on Web Conference 2025"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3696410.3714890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:53Z","timestamp":1750295933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,22]]},"references-count":74,"alternative-id":["10.1145\/3696410.3714890","10.1145\/3696410"],"URL":"https:\/\/doi.org\/10.1145\/3696410.3714890","relation":{},"subject":[],"published":{"date-parts":[[2025,4,22]]},"assertion":[{"value":"2025-04-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}