{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:41Z","timestamp":1778807861542,"version":"3.51.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Australian Research Council (ARC) Discovery Early Career Research Award","award":["DE190101118"],"award-info":[{"award-number":["DE190101118"]}]},{"name":"VILLUM Foundation Grant","award":["54451"],"award-info":[{"award-number":["54451"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>\n            In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set,\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            , of\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            items, where each item,\n            <jats:italic toggle=\"yes\">x<\/jats:italic>\n            , has a non-negative integer weight, w(x). Given a pair of query parameters, (\u03b1, \u03b2), each of which is a non-negative rational number, a parameterized subset sampling query on\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            seeks to return a subset T \u2286 S such that each item x\u2208 S is selected in\n            <jats:italic toggle=\"yes\">T<\/jats:italic>\n            , independently, with probability p_x(\u03b1, \u03b2) which is the minimum between 1 and w(x) \/ (\u03b1 \\cdot W + \u03b2), where\n            <jats:italic toggle=\"yes\">W<\/jats:italic>\n            is the total weight of the items in\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            . More specifically, the DPSS problem is defined in a dynamic setting, where the item set,\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            , can be updated with insertions of new items or deletions of existing items. Our first main result is an optimal algorithm for solving the DPSS problem, which achieves O(n) pre-processing time, O(1+\u03bc_S(\u03b1,\u03b2)) expected time for each query parameterized by (\u03b1, \u03b2), given on-the-fly, and O(1) time for each update; here, \u03bc_S(\u03b1,\u03b2) is the expected size of the query result. At all times, the worst-case space consumption of our algorithm is linear in the current number of items in\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            . Our second main contribution is a hardness result for the DPSS problem when the item weights are O(1)-word float numbers, rather than integers. Specifically, we reduce Integer Sorting to the deletion-only DPSS problem with float item weights. Our reduction shows that an optimal algorithm for deletion-only DPSS with float item weights (achieving all the same bounds as aforementioned) implies an algorithm for sorting\n            <jats:italic toggle=\"yes\">N<\/jats:italic>\n            integers in O(N) expected time. The latter remains an important open problem. Moreover, a deletion-only DPSS algorithm which supports float item weights, with complexities worse, by at most a factor of o(\u221a\u0142og \u0142og N), than the optimal counterparts, would already improve the current-best integer sorting algorithm [FOCS 2002]. Last but not least, a key technical ingredient for our first main result is a set of exact and efficient algorithms for generating Bernoulli (of certain forms) and Truncated Geometric random variates in O(1) expected time with O(n) worst-case space in the Word RAM model. Generating Bernoulli and geometric random variates efficiently is of great importance not only to sampling problems but also to encryption in cybersecurity. We believe that our new algorithms may be of independent interests for related research.\n          <\/jats:p>","DOI":"10.1145\/3695827","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-26","source":"Crossref","is-referenced-by-count":3,"title":["Optimal Dynamic Parameterized Subset Sampling"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9101-1503","authenticated-orcid":false,"given":"Junhao","family":"Gan","sequence":"first","affiliation":[{"name":"The University of Melbourne, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6984-4007","authenticated-orcid":false,"given":"Seeun William","family":"Umboh","sequence":"additional","affiliation":[{"name":"The University of Melbourne &amp; ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA), Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0995-5546","authenticated-orcid":false,"given":"Hanzhi","family":"Wang","sequence":"additional","affiliation":[{"name":"BARC, University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3746-6704","authenticated-orcid":false,"given":"Anthony","family":"Wirth","sequence":"additional","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4354-5681","authenticated-orcid":false,"given":"Zhuo","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of Melbourne, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2024. Optimal Dynamic Parameterized Subset Sampling. arXiv:2409.18036 [cs.DS]. Available at https:\/\/arxiv.org\/abs\/ 2409.18036."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2016.37"},{"key":"e_1_2_1_4_1","volume-title":"Scandinavian Workshop on Algorithm Theory. Springer, 26--37","author":"Belazzougui Djamal","year":"2014","unstructured":"Djamal Belazzougui, Gerth St\u00f8lting Brodal, and Jesper Sindahl Nielsen. 2014. Expected Linear Time Sorting for Word Size (log2 log log). In Scandinavian Workshop on Algorithm Theory. Springer, 26--37."},{"key":"e_1_2_1_5_1","volume-title":"Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. arXiv preprint arXiv:2306.11828","author":"Bhattacharya Sayan","year":"2023","unstructured":"Sayan Bhattacharya, Peter Kiss, Aaron Sidford, and David Wajc. 2023. Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. arXiv preprint arXiv:2306.11828 (2023)."},{"key":"e_1_2_1_6_1","volume-title":"Modern computer arithmetic","author":"Brent Richard P","unstructured":"Richard P Brent and Paul Zimmermann. 2010. Modern computer arithmetic. Vol. 18. Cambridge University Press."},{"key":"e_1_2_1_7_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Bringmann Karl","unstructured":"Karl Bringmann and Tobias Friedrich. 2013. Exact and efficient generation of geometric random variates and random graphs. In International Colloquium on Automata, Languages, and Programming. Springer, 267--278."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i8.16902"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90014-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2887054"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601266103"},{"key":"e_1_2_1_14_1","article-title":"A comparative study of various sorting algorithms","volume":"4","author":"Gill Sandeep Kaur","year":"2019","unstructured":"Sandeep Kaur Gill, Virendra Pal Singh, Pankaj Sharma, and Durgesh Kumar. 2019. A comparative study of various sorting algorithms. International Journal of Advanced Studies of Scientific Research 4, 1 (2019).","journal-title":"International Journal of Advanced Studies of Scientific Research"},{"key":"e_1_2_1_15_1","volume-title":"Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened. In SIGMOD Conference. ACM, 2167--2181","author":"Guo Qintian","year":"2020","unstructured":"Qintian Guo, Sibo Wang, Zhewei Wei, and Ming Chen. 2020. Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened. In SIGMOD Conference. ACM, 2167--2181."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533817"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ymssp.2018.12.035"},{"key":"e_1_2_1_18_1","volume-title":"IEEE Symposium on Foundations of Computer Science (FOCS'02)","author":"Han Yijie","year":"2002","unstructured":"Yijie Han and Mikkel Thorup. 2002. Sorting integers in ( log log) expected time and linear space. In IEEE Symposium on Foundations of Computer Science (FOCS'02)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10522"},{"key":"e_1_2_1_20_1","unstructured":"Taher Haveliwala et al. 1999. Efficient computation of PageRank. Technical Report. Citeseer."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Brendan Juba Christopher Musco Fan Long Stelios Sidiroglou-Douskos and Martin C Rinard. 2015. Principled Sampling for Anomaly Detection.. In NDSS.","DOI":"10.14722\/ndss.2015.23268"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Alexander D Kent. 2016. Cyber security data sources for dynamic network research. In Dynamic Networks and Cyber-Security. World Scientific 37--65.","DOI":"10.1142\/9781786340757_0002"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.6029\/smartcr.2014.03.007"},{"key":"e_1_2_1_24_1","volume-title":"International conference on machine learning. PMLR, 2320--2329","author":"Liberty Edo","year":"2016","unstructured":"Edo Liberty, Kevin Lang, and Konstantin Shmakov. 2016. Stratified sampling meets machine learning. In International conference on machine learning. PMLR, 2320--2329."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1177080.1177102"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.31"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.21511\/imfi.16(1).2019.22"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467243"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/DNSR.2004.1344743"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319886"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599458"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00088"},{"key":"e_1_2_1_34_1","unstructured":"Lingling Zhang Hong Jiang Ye Yuan and Guoren Wang. 2024. Influence Maximization in Hypergraphs by Stratified Sampling for Efficient Generation of Reverse Reachable Sets. arXiv preprint arXiv:2406.01911 (2024)"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695827","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695827","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:33:32Z","timestamp":1755916412000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695827"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695827"],"URL":"https:\/\/doi.org\/10.1145\/3695827","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}