{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:42:11Z","timestamp":1787017331839,"version":"build-2736575974"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:00:00Z","timestamp":1662768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>\n                    Data structures for efficient sampling from a set of weighted items are an important building block of many applications. However, few parallel solutions are known. We close many of these gaps. We give efficient, fast, and practicable parallel and distributed algorithms for building data structures that support sampling single items (alias tables, compressed data structures). This also yields a simplified and more space-efficient sequential algorithm for alias table construction. Our approaches to sampling\n                    <jats:italic>k<\/jats:italic>\n                    out of\n                    <jats:italic>n<\/jats:italic>\n                    items with\/without replacement and to subset (Poisson) sampling are\n                    <jats:italic>output-sensitive<\/jats:italic>\n                    , i.e., the sampling algorithms use work linear in the number of\n                    <jats:italic>different<\/jats:italic>\n                    samples. This is also interesting in the sequential case. Weighted random permutation can be done by sorting appropriate random deviates. We show that this is possible with linear work. Finally, we give a communication-efficient, highly scalable approach to (weighted and unweighted) reservoir sampling. This algorithm is based on a fully distributed model of streaming algorithms that might be of independent interest. Experiments for alias tables and sampling with replacement show near linear speedups using up to 158 threads of shared-memory machines. An experimental evaluation of distributed weighted reservoir sampling on up to 5,120 cores also shows good speedups.\n                  <\/jats:p>","DOI":"10.1145\/3549934","type":"journal-article","created":{"date-parts":[[2022,7,22]],"date-time":"2022-07-22T07:19:46Z","timestamp":1658474386000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Parallel Weighted Random Sampling"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4315-3264","authenticated-orcid":false,"given":"Lorenz","family":"H\u00fcbschle-Schneider","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3330-9349","authenticated-orcid":false,"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,9,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214402"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2016.042"},{"key":"e_1_3_2_4_2","first-page":"29","article-title":"On the amount of dependence in the prime factorization of a uniform random integer","volume":"10","author":"Arratia Richard","year":"2002","unstructured":"Richard Arratia. 2002. On the amount of dependence in the prime factorization of a uniform random integer. Contemporary Combinatorics 10 (2002), 29\u201391. Page 36.","journal-title":"Contemporary Combinatorics"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1468075.1468121"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.16\""},{"key":"e_1_3_2_7_2","unstructured":"Timo Bingmann. 2018. TLX: Collection of Sophisticated C++ Data Structures Algorithms and Miscellaneous Helpers. https:\/\/panthema.net\/tlx."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2016.7840603"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.42122"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.07.007"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9407-5"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1145\/2488608.2488707","volume-title":"45th ACM Symposium on Theory of Computing (STOC)","author":"Bringmann Karl","year":"2013","unstructured":"Karl Bringmann and Kasper Green Larsen. 2013. Succinct sampling from discrete distributions. In 45th ACM Symposium on Theory of Computing (STOC). ACM, 775\u2013782."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0205-0"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/69.3.653"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129081\""},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2518679"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2481528.2481530"},{"key":"e_1_3_2_21_2","first-page":"77","volume-title":"29th ACM Symposium on Principles of Database Systems (PODS\u201910)","author":"Cormode Graham","year":"2010","unstructured":"Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang. 2010. Optimal sampling from distributed streams. In 29th ACM Symposium on Principles of Database Systems (PODS\u201910). ACM, 77\u201386."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160163"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/299633.299634"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-319-24024-4_12","volume-title":"Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday","author":"Efraimidis Pavlos S.","year":"2015","unstructured":"Pavlos S. Efraimidis. 2015. Weighted random sampling over data streams. In Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday. Springer, 183\u2013195."},{"key":"e_1_3_2_27_2","volume-title":"Fast Parallel Weighted Random Sampling","author":"Efraimidis Pavlos S.","year":"1999","unstructured":"Pavlos S. Efraimidis and Paul G. Spirakis. 1999. Fast Parallel Weighted Random Sampling. Technical Report TR99.04.02. CTI Patras."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/1138831.1711169"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1962.10480667"},{"key":"e_1_3_2_30_2","volume-title":"GNU Scientific Library: Reference Manual (3rd ed.)","author":"Galassi Mark","year":"2009","unstructured":"Mark Galassi, Jim Davies, James Theiler, Brian Gough, Gerard Jungmann, Patrick Alken, Michael Booth, Fabrice Rossi, and Rhys Ulerich. 2009. GNU Scientific Library: Reference Manual (3rd ed.). Network Theory."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185569"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676201\""},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/3-540-54233-7_151","volume-title":"18th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Hagerup Torben","year":"1991","unstructured":"Torben Hagerup. 1991. Fast parallel generation of random permutations. In 18th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 405\u2013416."},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/3-540-56939-1_77","volume-title":"20th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Hagerup Torben","year":"1993","unstructured":"Torben Hagerup, Kurt Mehlhorn, and J. Ian Munro. 1993. Maintaining discrete probability distributions optimally. In 20th International Colloquium on Automata, Languages, and Programming (ICALP). Springer, 253\u2013264."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177700375"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731356"},{"key":"e_1_3_2_37_2","volume-title":"On Asymptotic Notation with Multiple Variables","author":"Howell Rodney R.","year":"2008","unstructured":"Rodney R. Howell. 2008. On Asymptotic Notation with Multiple Variables. Technical Report 2007-4. Kansas State University."},{"key":"e_1_3_2_38_2","first-page":"659","volume-title":"30th International Parallel and Distributed Processing Symposium (IPDPS)","author":"H\u00fcbschle-Schneider Lorenz","year":"2016","unstructured":"Lorenz H\u00fcbschle-Schneider and Peter Sanders. 2016. Communication efficient algorithms for top- \\( k \\) selection problems. In 30th International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 659\u2013668."},{"key":"e_1_3_2_39_2","volume-title":"27th European Symposium on Algorithms (ESA)","author":"H\u00fcbschle-Schneider Lorenz","year":"2019","unstructured":"Lorenz H\u00fcbschle-Schneider and Peter Sanders. 2019. Parallel weighted random sampling. In 27th European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.5445\/IR\/1000127719\""},{"key":"e_1_3_2_41_2","volume-title":"32nd ACM Symp. on Parallelism in Algorithms and Architectures (SPAA)","author":"H\u00fcbschle-Schneider Lorenz","year":"2020","unstructured":"Lorenz H\u00fcbschle-Schneider and Peter Sanders. 2020. Communication-efficient weighted reservoir sampling from fully distributed data streams. In 32nd ACM Symp. on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_42_2","article-title":"Communication efficient algorithms for top- \\( k \\)  selection problems","author":"H\u00fcbschle-Schneider Lorenz","year":"2015","unstructured":"Lorenz H\u00fcbschle-Schneider, Peter Sanders, and Ingo M\u00fcller. 2015. Communication efficient algorithms for top- \\( k \\) selection problems. Computing Research Repository (CoRR) (2 2015). arxiv:1502.03942 [cs.DS]","journal-title":"Computing Research Repository (CoRR)"},{"key":"e_1_3_2_43_2","volume-title":"Intel Math Kernel Library 2019","year":"2019","unstructured":"Intel. 2019. Intel Math Kernel Library 2019. Intel. https:\/\/software.intel.com\/en-us\/mkl-reference-manual-for-c."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.5555\/133889"},{"key":"e_1_3_2_45_2","first-page":"218","volume-title":"38th ACM Symposium on Principles of Database Systems (PODS\u201919)","author":"Jayaram Rajesh","year":"2019","unstructured":"Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, and David P. Woodruff. 2019. Weighted reservoir sampling from distributed streams. In 38th ACM Symposium on Principles of Database Systems (PODS\u201919). ACM, 218\u2013235."},{"key":"e_1_3_2_46_2","volume-title":"Introduction to Parallel Computing. Design and Analysis of Algorithms","author":"Kumar Vipin","year":"1994","unstructured":"Vipin Kumar, Ananth Grama, Anshul Gupta, and George Karypis. 1994. Introduction to Parallel Computing. Design and Analysis of Algorithms. Benjamin\/Cummings."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9496-6"},{"key":"e_1_3_2_48_2","volume-title":"Weighted Random Sampling: Alias Tables on the GPU","author":"Lehmann Hans-Peter","year":"2020","unstructured":"Hans-Peter Lehmann. 2020. Weighted Random Sampling: Alias Tables on the GPU. Master\u2019s thesis. Karlsruhe Institute of Technology (KIT)."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/198429.198435"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v011.i03"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1078-6"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/272991.272995"},{"key":"e_1_3_2_53_2","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/978-3-540-72845-0_19","volume-title":"6th Workshop on Experimental Algorithms (WEA)","author":"Maue Jens","year":"2007","unstructured":"Jens Maue and Peter Sanders. 2007. Engineering algorithms for approximate weighted matching. In 6th Workshop on Experimental Algorithms (WEA). Springer, 242\u2013255."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_3_2_55_2","article-title":"Accelerating weighted random sampling without replacement","volume":"1141","author":"M\u00fcller Kirill","year":"2016","unstructured":"Kirill M\u00fcller. 2016. Accelerating weighted random sampling without replacement. Arbeitsberichte Verkehrs-und Raumplanung 1141 (2016).","journal-title":"Arbeitsberichte Verkehrs-und Raumplanung"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00140664"},{"key":"e_1_3_2_57_2","volume-title":"R: A Language and Environment for Statistical Computing","author":"Team R Core","year":"2019","unstructured":"R Core Team. 2019. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. https:\/\/www.R-project.org."},{"key":"e_1_3_2_58_2","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/3-540-49543-6_13","volume-title":"International Workshop on Randomization and Approximation Techniques in Computer Science","author":"Raab Martin","year":"1998","unstructured":"Martin Raab and Angelika Steger. 1998. \u201cBalls into bins\u201d-A simple and tight analysis. In International Workshop on Randomization and Approximation Techniques in Computer Science. Springer, 159\u2013170."},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218041"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90005-P"},{"key":"e_1_3_2_61_2","volume-title":"First Workshop on Randomized Parallel Algorithms","author":"Sanders Peter","year":"1996","unstructured":"Peter Sanders. 1996. On the competitive analysis of randomized static load balancing. In First Workshop on Randomized Parallel Algorithms, S. Rajasekaran (Ed.). Honolulu, Hawaii. http:\/\/algo2.iti.kit.edu\/sanders\/papers\/rand96.pdf."},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00127-6"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3157734"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.5555\/3378988"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691549"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2017.85"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.2307\/2346966"},{"key":"e_1_3_2_68_2","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/978-3-030-29400-7_32","volume-title":"Euro-Par 2019: Parallel Processing","author":"Tangwongsan Kanat","year":"2019","unstructured":"Kanat Tangwongsan and Srikanta Tirthapura. 2019. Parallel streaming random sampling. In Euro-Par 2019: Parallel Processing. Springer, 451\u2013465."},{"key":"e_1_3_2_69_2","volume-title":"Sampling Algorithms","author":"Till\u00e9 Yves","year":"2006","unstructured":"Yves Till\u00e9. 2006. Sampling Algorithms. Springer."},{"key":"e_1_3_2_70_2","first-page":"283","volume-title":"25th International Symposium on Distributed Computing (DISC\u201911)","author":"Tirthapura Srikanta","year":"2011","unstructured":"Srikanta Tirthapura and David P. Woodruff. 2011. Optimal random sampling from distributed streams revisited. In 25th International Symposium on Distributed Computing (DISC\u201911). Springer, 283\u2013297."},{"key":"e_1_3_2_71_2","volume-title":"Annual Survey of Manufactures Methodology","author":"Bureau U.S. Census","year":"2021","unstructured":"U.S. Census Bureau. 2021. Annual Survey of Manufactures Methodology. https:\/\/www.census.gov\/programs-surveys\/asm\/technical-documentation\/methodology.html."},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209009"},{"key":"e_1_3_2_76_2","first-page":"423","volume-title":"24th ACM Symposium on Operating Systems Principles (SOSP)","author":"Zaharia Matei","year":"2013","unstructured":"Matei Zaharia et\u00a0al. 2013. Discretized streams: Fault-tolerant streaming computation at scale. In 24th ACM Symposium on Operating Systems Principles (SOSP). ACM, 423\u2013438."},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549934","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3549934","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T14:08:13Z","timestamp":1750169293000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549934"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,10]]},"references-count":76,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3549934"],"URL":"https:\/\/doi.org\/10.1145\/3549934","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,10]]},"assertion":[{"value":"2020-06-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}