{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:00:03Z","timestamp":1772042403929,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,1,3]],"date-time":"2018-01-03T00:00:00Z","timestamp":1514937600000},"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":[[2018,9,30]]},"abstract":"<jats:p>\n            We consider the problem of sampling\n            <jats:italic>n<\/jats:italic>\n            numbers from the range { 1,\u2026 ,\n            <jats:italic>N<\/jats:italic>\n            } without replacement on modern architectures. The main result is a simple divide-and-conquer scheme that makes sequential algorithms more cache efficient and leads to a parallel algorithm running in expected time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>p<\/jats:italic>\n            +log\n            <jats:italic>p<\/jats:italic>\n            ) on\n            <jats:italic>p<\/jats:italic>\n            processors, i.e., scales to massively parallel machines even for moderate values of\n            <jats:italic>n<\/jats:italic>\n            . The amount of communication between the processors is very small (at most\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>p<\/jats:italic>\n            )) and independent of the sample size. We also discuss modifications needed for load balancing, online sampling, sampling with replacement, Bernoulli sampling, and vectorization on SIMD units or GPUs.\n          <\/jats:p>","DOI":"10.1145\/3157734","type":"journal-article","created":{"date-parts":[[2018,1,4]],"date-time":"2018-01-04T16:27:31Z","timestamp":1515083251000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Efficient Parallel Random Sampling\u2014Vectorized, Cache-Efficient, and Online"],"prefix":"10.1145","volume":"44","author":[{"given":"Peter","family":"Sanders","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Lamm","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4315-3264","authenticated-orcid":false,"given":"Lorenz","family":"H\u00fcbschle-Schneider","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuel","family":"Schrade","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Dachsbacher","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214402"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755595"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/113379.113380"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209958"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_1_6_1","unstructured":"D. G. Brown. 2011. How I wasted too long finding a concentration inequality for sums of geometric variables. Retrieved from https:\/\/cs.uwaterloo.ca\/&sim;browndg\/negbin.pdf.  D. G. Brown. 2011. How I wasted too long finding a concentration inequality for sums of geometric variables. Retrieved from https:\/\/cs.uwaterloo.ca\/&sim;browndg\/negbin.pdf."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs","volume":"6","author":"Erd\u00f6s P.","year":"1959","unstructured":"P. Erd\u00f6s and A. R\u00e9nyi . 1959 . On random graphs , I. Publ. Math. (Debrecen) 6 (1959), 290 -- 297 . P. Erd\u00f6s and A. R\u00e9nyi. 1959. On random graphs, I. Publ. Math. (Debrecen) 6 (1959), 290--297.","journal-title":"I. Publ. Math. (Debrecen)"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1962.10480667"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/22719.24067"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00043"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824069"},{"key":"e_1_2_1_12_1","unstructured":"Intel. 2012. Intel Digital Random Number Generator (DRNG): Software Implementation Guide. Intel. Retrieved from https:\/\/software.intel.com\/en-us\/articles\/intel-digital-random-number-generator-drng-software-implementation-guide.  Intel. 2012. Intel Digital Random Number Generator (DRNG): Software Implementation Guide. Intel. Retrieved from https:\/\/software.intel.com\/en-us\/articles\/intel-digital-random-number-generator-drng-software-implementation-guide."},{"key":"e_1_2_1_13_1","unstructured":"Intel. 2015. Intel Math Kernel Library v11.3. Intel. Retrieved from https:\/\/software.intel.com\/en-us\/mkl-reference-manual-for-c.  Intel. 2015. Intel Math Kernel Library v11.3. Intel. Retrieved from https:\/\/software.intel.com\/en-us\/mkl-reference-manual-for-c."},{"key":"e_1_2_1_14_1","volume-title":"The Art of Computer Programming\u2014Seminumerical Algorithms","author":"Knuth D. E.","unstructured":"D. E. Knuth . 1981. The Art of Computer Programming\u2014Seminumerical Algorithms , 2 nd ed. Vol. 2 . Addison--Wesley . D. E. Knuth. 1981. The Art of Computer Programming\u2014Seminumerical Algorithms, 2nd ed. Vol. 2. Addison--Wesley.","edition":"2"},{"key":"e_1_2_1_15_1","volume-title":"The Art of Computer Programming\u2014Sorting and Searching","author":"Knuth D. E.","unstructured":"D. E. Knuth . 1998. The Art of Computer Programming\u2014Sorting and Searching , 2 nd ed. Vol. 3 . Addison--Wesley . D. E. Knuth. 1998. The Art of Computer Programming\u2014Sorting and Searching, 2nd ed. Vol. 3. Addison--Wesley.","edition":"2"},{"key":"e_1_2_1_16_1","volume-title":"Communication Efficient Algorithms for Generating Massive Networks. Master\u2019s thesis","author":"Lamm S.","unstructured":"S. Lamm . 2017. Communication Efficient Algorithms for Generating Massive Networks. Master\u2019s thesis . Karlsruhe Institute of Technology . S. Lamm. 2017. Communication Efficient Algorithms for Generating Massive Networks. Master\u2019s thesis. Karlsruhe Institute of Technology."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/272991.272995"},{"key":"e_1_2_1_18_1","volume-title":"Int. Conf. on Machine Learning (ICML\u201913)","author":"Meng X.","year":"2013","unstructured":"X. Meng . 2013 . Scalable simple random sampling and stratified sampling . In Int. Conf. on Machine Learning (ICML\u201913) . 531--539. X. Meng. 2013. Scalable simple random sampling and stratified sampling. In Int. Conf. on Machine Learning (ICML\u201913). 531--539."},{"key":"e_1_2_1_19_1","unstructured":"P. Sanders. 1996. Lastverteilungsalgorithmen f\u00fcr parallele Tiefensuche. Dissertation. Universit\u00e4t Karlsruhe.  P. Sanders. 1996. Lastverteilungsalgorithmen f\u00fcr parallele Tiefensuche. Dissertation. Universit\u00e4t Karlsruhe."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/45.5.561"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE International Conference on Big Data. 15--23","author":"Sanders P.","unstructured":"P. Sanders , S. Schlag , and I. M\u00fcller . 2013. Communication efficient algorithms for fundamental big data problems . In Proceedings of the IEEE International Conference on Big Data. 15--23 . P. Sanders, S. Schlag, and I. M\u00fcller. 2013. Communication efficient algorithms for fundamental big data problems. In Proceedings of the IEEE International Conference on Big Data. 15--23."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536251"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 13th Int. Euro-Par Conf. (LNCS)","volume":"4641","author":"Singler J.","unstructured":"J. Singler , P. Sanders , and F. Putze . 2007. MCSTL: The multi-core standard template library . In Proceedings of the 13th Int. Euro-Par Conf. (LNCS) , Vol. 4641 . Springer, 682--694. J. Singler, P. Sanders, and F. Putze. 2007. MCSTL: The multi-core standard template library. In Proceedings of the 13th Int. Euro-Par Conf. (LNCS), Vol. 4641. Springer, 682--694."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(90)90349-5"},{"key":"e_1_2_1_25_1","volume-title":"JUQUEEN: IBM Blue Gene\/Q supercomputer system at the J\u00fclich Supercomputing Centre. Journal of Large-scale Research Facilities A1 (1","author":"Stephan M.","year":"2015","unstructured":"M. Stephan and J. Docter . 2015 . J\u00fclich supercomputing centre. JUQUEEN: IBM Blue Gene\/Q supercomputer system at the J\u00fclich Supercomputing Centre. Journal of Large-scale Research Facilities A1 (1 2015), 1\u20135. M. Stephan and J. Docter. 2015. J\u00fclich supercomputing centre. JUQUEEN: IBM Blue Gene\/Q supercomputer system at the J\u00fclich Supercomputing Centre. Journal of Large-scale Research Facilities A1 (1 2015), 1\u20135."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800255.810659"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/358105.893"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3157734","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3157734","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:30Z","timestamp":1750212690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3157734"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,3]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3157734"],"URL":"https:\/\/doi.org\/10.1145\/3157734","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,3]]},"assertion":[{"value":"2016-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}