{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:31Z","timestamp":1781326711508,"version":"3.54.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    Our ability to collect data is rapidly surpassing our ability to store it. As a result, organizations are faced with difficult decisions about which data to retain and which to dispose of. Data forgetting, frames this reduction task as a subset selection exercise. Given a relational dataset\n                    <jats:italic toggle=\"yes\">D<\/jats:italic>\n                    , a query log\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    , and a budget\n                    <jats:italic toggle=\"yes\">B<\/jats:italic>\n                    , the goal is to find a subset D^* \u2286 D with at most\n                    <jats:italic toggle=\"yes\">B<\/jats:italic>\n                    tuples such that it is still possible to compute, based solely on D^*, approximate answers to the expected query workload. Existing data forgetting routines have substantial limitations. They either offer strong theoretical guarantees but lack scalability due to function evaluation (submodular-based), or achieve scalability by avoiding function evaluation but lack theoretical guarantees (amnesia-based). To bridge the gap between the limitations of submodular and amnesia based methods, we propose\n                    <jats:italic toggle=\"yes\">IndepDF<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">DepDF<\/jats:italic>\n                    : two data forgetting routines that offer scalability by avoiding function evaluation while maintaining strong theoretical guarantees. Our extensive experimental evaluation on real and synthetic datasets demonstrates that our algorithms are capable of matching the performance of the state-of-the-art submodular-based routines while exhibiting a runtime comparable to that of amnesia-based algorithms. In essence, combining the best traits of both.\n                  <\/jats:p>","DOI":"10.1145\/3769830","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-22","source":"Crossref","is-referenced-by-count":0,"title":["Stochastic Submodular Data Forgetting"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-6587-394X","authenticated-orcid":false,"given":"Ramon","family":"Rico","sequence":"first","affiliation":[{"name":"Utrecht University, Utrecht, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5108-7965","authenticated-orcid":false,"given":"Arno","family":"Siebes","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6332-0296","authenticated-orcid":false,"given":"Yannis","family":"Velegrakis","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"496","article-title":"Automated selection of materialized views and indexes in SQL databases","volume":"2000","author":"Agrawal Sanjay","year":"2000","unstructured":"Sanjay Agrawal, Surajit Chaudhuri, and Vivek R Narasayya. 2000. Automated selection of materialized views and indexes in SQL databases. In VLDB, Vol. 2000. 496-505.","journal-title":"VLDB"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-018-1183-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056097"},{"key":"e_1_2_1_5_1","volume-title":"Sampling Techniques","author":"Cochran William G.","unstructured":"William G. Cochran. 1977. Sampling Techniques, 3rd Edition., John Wiley.","edition":"3"},{"key":"e_1_2_1_6_1","first-page":"9","article-title":"Data","volume":"60","author":"Cormode Graham","year":"2017","unstructured":"Graham Cormode. 2017. Data Sketching. Commun. ACM, Vol. 60, 9 (aug 2017), 48-55.","journal-title":"Sketching. Commun. ACM"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601985170"},{"key":"e_1_2_1_8_1","volume-title":"Disposal by Design. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering","author":"Davidson Susan B.","year":"2022","unstructured":"Susan B. Davidson, Shay Gershtein, Tova Milo, and Slava Novgorodov. 2022a. Disposal by Design. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering (2022)."},{"key":"e_1_2_1_9_1","first-page":"12","article-title":"PHOcus","volume":"15","author":"Davidson Susan B.","year":"2022","unstructured":"Susan B. Davidson, Shay Gershtein, Tova Milo, Slava Novgorodov, and May Shoshan. 2022b. PHOcus: Efficiently Archiving Photos. Proc. VLDB Endow., Vol. 15, 12 (sep 2022), 3630-3633.","journal-title":"Efficiently Archiving Photos. Proc. VLDB Endow."},{"key":"e_1_2_1_10_1","volume-title":"Efficiently Archiving Photos under Storage Constraints. EDBT","author":"Davidson Susan B","year":"2023","unstructured":"Susan B Davidson, Shay Gershtein, Tova Milo, Slava Novgorodov, and May Shoshan. 2023. Efficiently Archiving Photos under Storage Constraints. EDBT (2023)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467348"},{"key":"e_1_2_1_12_1","first-page":"645927","article-title":"Approximate Query Processing: Taming the TeraBytes","volume":"10","author":"Garofalakis Minos N","year":"2001","unstructured":"Minos N Garofalakis and Phillip B Gibbons. 2001. Approximate Query Processing: Taming the TeraBytes.. In VLDB, Vol. 10. 645927-672356.","journal-title":"VLDB"},{"key":"e_1_2_1_13_1","first-page":"522","article-title":"Inventory Reduction via Maximal Coverage in E-Commerce","author":"Gershtein Shay","year":"2020","unstructured":"Shay Gershtein, Tova Milo, and Slava Novgorodov. 2020. Inventory Reduction via Maximal Coverage in E-Commerce.. In EDBT. 522-533.","journal-title":"EDBT."},{"key":"e_1_2_1_14_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Hassani Hamed","year":"2017","unstructured":"Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. 2017. Gradient methods for submodular maximization. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.90"},{"key":"e_1_2_1_16_1","volume-title":"Global data storage and manufacturing capacity is critically low. The Holon Data Report, Part 5","author":"Investments Holon","year":"2023","unstructured":"Holon Investments. 2023. Global data storage and manufacturing capacity is critically low. The Holon Data Report, Part 5 (2023)."},{"key":"e_1_2_1_17_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Karimi Mohammad","year":"2017","unstructured":"Mohammad Karimi, Mario Lucic, Hamed Hassani, and Andreas Krause. 2017. Stochastic submodular maximization: The case of coverage functions. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303993"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 7th CIDR.","author":"Kersten Martin","year":"2015","unstructured":"Martin Kersten. 2015. Big Data Space Fungus. In Proceedings of the 7th CIDR."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 32nd ICDE.","author":"Kersten Martin","year":"2016","unstructured":"Martin Kersten. 2016. Keynote: DataFungi, from Rotting Data to Purified Information.. In Proceedings of the 32nd ICDE."},{"key":"e_1_2_1_21_1","unstructured":"Martin Kersten and Lefteris Sidirourgos. 2017. A Database System with Amnesia. In CIDR."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139177801.004"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-020-01316-z"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-018-0074-4"},{"key":"e_1_2_1_25_1","volume-title":"Learning mixtures of submodular shells with application to document summarization. arXiv preprint arXiv:1210.4871","author":"Lin Hui","year":"2012","unstructured":"Hui Lin and Jeff A Bilmes. 2012. Learning mixtures of submodular shells with application to document summarization. arXiv preprint arXiv:1210.4871 (2012)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-39940-9_534"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206874"},{"key":"e_1_2_1_28_1","article-title":"Getting Rid of Data","volume":"12","author":"Milo Tova","year":"2019","unstructured":"Tova Milo. 2019. Getting Rid of Data. J. Data and Information Quality, Vol. 12, 1, Article 1 (nov 2019), 7 pages.","journal-title":"J. Data and Information Quality"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0006528"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375703"},{"key":"e_1_2_1_31_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR","author":"Mokhtari Aryan","year":"2018","unstructured":"Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. 2018. Conditional gradient method for stochastic submodular maximization: Closing the gap. In International Conference on Artificial Intelligence and Statistics. PMLR, 1886-1895."},{"key":"e_1_2_1_32_1","volume-title":"An analysis of approximations for maximizing submodular set functions-I. Mathematical programming","author":"Nemhauser George L","year":"1978","unstructured":"George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978. An analysis of approximations for maximizing submodular set functions-I. Mathematical programming, Vol. 14 (1978), 265-294."},{"key":"e_1_2_1_33_1","volume-title":"On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science","author":"Pearson Karl","year":"1901","unstructured":"Karl Pearson. 1901. LIII. On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science, Vol. 2, 11 (1901), 559-572."},{"key":"e_1_2_1_34_1","volume-title":"Handbook of discrete and computational geometry","author":"Phillips Jeff M","unstructured":"Jeff M Phillips. 2017. Coresets and sketches. In Handbook of discrete and computational geometry. Chapman and Hall\/CRC, 1269-1288."},{"key":"e_1_2_1_35_1","volume-title":"Data Age 2025 - The digitization of the world from edge to core. Seagate","author":"Reinsel David","year":"2018","unstructured":"David Reinsel, John Gantz, and John Rydning. 2018. Data Age 2025 - The digitization of the world from edge to core. Seagate (2018)."},{"key":"e_1_2_1_36_1","first-page":"488","article-title":"Materialized view selection for multidimensional datasets","volume":"98","author":"Shukla Amit","year":"1998","unstructured":"Amit Shukla, Prasad Deshpande, Jeffrey F Naughton, et al., 1998. Materialized view selection for multidimensional datasets. In VLDB, Vol. 98. 488-499.","journal-title":"VLDB"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2007.4408863"},{"key":"e_1_2_1_38_1","volume-title":"Weinberger (Eds.)","volume":"27","author":"Tschiatschek Sebastian","year":"2014","unstructured":"Sebastian Tschiatschek, Rishabh K Iyer, Haochen Wei, and Jeff A Bilmes. 2014. Learning Mixtures of Submodular Functions for Image Collection Summarization. In Advances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (Eds.), Vol. 27. Curran Associates, Inc."},{"key":"e_1_2_1_39_1","volume-title":"Upton and Patrick Cook","author":"Graham J.","year":"2002","unstructured":"Graham J. G. Upton and Patrick Cook. 2002. A Dictionary of Statistics."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32129-0_26"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769830","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:46:41Z","timestamp":1781326001000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769830"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769830"],"URL":"https:\/\/doi.org\/10.1145\/3769830","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}