{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T09:30:49Z","timestamp":1775899849705,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384259","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1265-1278","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast hashing with strong concentration bounds"],"prefix":"10.1145","author":[{"given":"Anders","family":"Aamand","sequence":"first","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakob B\u00e6k Tejs","family":"Knudsen","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias B\u00e6k Tejs","family":"Knudsen","sequence":"additional","affiliation":[{"name":"SupWiz, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Michael Reichstein","family":"Rasmussen","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"No Repetitions: Fast Streaming with Highly Concentrated Hashing. ArXiv, abs\/2004.01156.","author":"Aamand Anders","year":"2020","unstructured":"Anders Aamand , Evangelos Kipouridis , Jakob B. T. Knudsen , Peter M. R. Rasmussen , and Mikkel Thorup . 2020 . No Repetitions: Fast Streaming with Highly Concentrated Hashing. ArXiv, abs\/2004.01156. Anders Aamand, Evangelos Kipouridis, Jakob B. T. Knudsen, Peter M. R. Rasmussen, and Mikkel Thorup. 2020. No Repetitions: Fast Streaming with Highly Concentrated Hashing. ArXiv, abs\/2004.01156."},{"key":"e_1_3_2_1_2_1","volume-title":"Mathias B. T. Knudsen, Peter M. R. Rasmussen, and Mikkel Thorup.","author":"Aamand Anders","year":"2019","unstructured":"Anders Aamand , Jakob B\u00e6 k Tejs Knudsen , Mathias B. T. Knudsen, Peter M. R. Rasmussen, and Mikkel Thorup. 2019 . Fast hashing with Strong Concentration Bounds. ArXiv , abs\/1905.00369 (2019). Anders Aamand, Jakob B\u00e6 k Tejs Knudsen, Mathias B. T. Knudsen, Peter M. R. Rasmussen, and Mikkel Thorup. 2019. Fast hashing with Strong Concentration Bounds. ArXiv, abs\/1905.00369 (2019)."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548503"},{"key":"e_1_3_2_1_4_1","unstructured":"Austin Appleby. 2016. MurmurHash3.  Austin Appleby. 2016. MurmurHash3."},{"key":"e_1_3_2_1_5_1","volume-title":"Smaller, Fast as MD5","author":"Aumasson Jean-Philippe","unstructured":"Jean-Philippe Aumasson , Samuel Neves , Zooko Wilcox-O\u2019Hearn , and Christian Winnerlein . 2013. BLAKE2 : Simpler , Smaller, Fast as MD5 . In Applied Cryptography and Network Security, Michael Jacobson, Michael Locasto, Payman Mohassel, and Reihaneh Safavi-Naini (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 119\u2013135. isbn:978-3-642-38980-1 Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O\u2019Hearn, and Christian Winnerlein. 2013. BLAKE2: Simpler, Smaller, Fast as MD5. In Applied Cryptography and Network Security, Michael Jacobson, Michael Locasto, Payman Mohassel, and Reihaneh Safavi-Naini (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 119\u2013135. isbn:978-3-642-38980-1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1962.10482149"},{"key":"e_1_3_2_1_8_1","first-page":"38","article-title":"On a modification of Chebyshev\u2019s inequality and of the error formula of","author":"Bernstein Sergei Natanovich","year":"1924","unstructured":"Sergei Natanovich Bernstein . 1924 . On a modification of Chebyshev\u2019s inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math. , 38 \u2013 49 . Sergei Natanovich Bernstein. 1924. On a modification of Chebyshev\u2019s inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math., 38\u201349.","journal-title":"Laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math."},{"key":"e_1_3_2_1_9_1","unstructured":"Andrei Z. Broder. 1997. On the resemblance and containment of documents. In Compression and Complexity of Sequences (SEQUENCES). 21\u201329.  Andrei Z. Broder. 1997. On the resemblance and containment of documents. In Compression and Complexity of Sequences (SEQUENCES). 21\u201329."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_3_2_1_11_1","volume-title":"Balls and Bins: Smaller Hash Families and Faster Evaluation. In 52nd Annual Symposium on Foundations of Computer Science (FOCS). 599\u2013608","author":"Celis L. Elisa","year":"2011","unstructured":"L. Elisa Celis , Omer Reingold , Gil Segev , and Udi Wieder . 2011 . Balls and Bins: Smaller Hash Families and Faster Evaluation. In 52nd Annual Symposium on Foundations of Computer Science (FOCS). 599\u2013608 . L. Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder. 2011. Balls and Bins: Smaller Hash Families and Faster Evaluation. In 52nd Annual Symposium on Foundations of Computer Science (FOCS). 599\u2013608."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213028"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.29"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746620"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a030"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.83"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS). Curran Associates Inc., 6618\u20136628","author":"Dahlgaard S\u00f8ren","year":"2017","unstructured":"S\u00f8ren Dahlgaard , Mathias B\u00e6 k Tejs Knudsen , and Mikkel Thorup . 2017 . Practical Hash Functions for Similarity Estimation and Dimensionality Reduction . In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS). Curran Associates Inc., 6618\u20136628 . isbn:978-1-5108-6096-4 http:\/\/dl.acm.org\/citation.cfm?id=3295222.3295407 S\u00f8ren Dahlgaard, Mathias B\u00e6 k Tejs Knudsen, and Mikkel Thorup. 2017. Practical Hash Functions for Similarity Estimation and Dimensionality Reduction. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS). Curran Associates Inc., 6618\u20136628. isbn:978-1-5108-6096-4 http:\/\/dl.acm.org\/citation.cfm?id=3295222.3295407"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/646511.695324"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-95233-2_7"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_30"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780634"},{"key":"e_1_3_2_1_24_1","first-page":"6","article-title":"Indexing for rapid random access memory systems","volume":"5","author":"Dumey A. I.","year":"1956","unstructured":"A. I. Dumey . 1956 . Indexing for rapid random access memory systems . Computers and Automation , 5 , 12 (1956), 6 \u2013 9 . A. I. Dumey. 1956. Indexing for rapid random access memory systems. Computers and Automation, 5, 12 (1956), 6\u20139.","journal-title":"Computers and Automation"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1195-x"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1062132"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646515.695985"},{"key":"e_1_3_2_1_28_1","volume-title":"Patterson","author":"Hennessy John L.","year":"2012","unstructured":"John L. Hennessy and David A . Patterson . 2012 . Computer Architecture - A Quantitative Approach, 5 th Edition. Morgan Kaufmann . isbn:978-0-12-383872-8 John L. Hennessy and David A. Patterson. 2012. Computer Architecture - A Quantitative Approach, 5th Edition. Morgan Kaufmann. isbn:978-0-12-383872-8","edition":"5"},{"key":"e_1_3_2_1_29_1","unstructured":"Donald E. Knuth. 1963. Notes on open addressing. Unpublished memorandum. See http:\/\/citeseer.ist.psu.edu\/knuth63notes.html.  Donald E. Knuth. 1963. Notes on open addressing. Unpublished memorandum. See http:\/\/citeseer.ist.psu.edu\/knuth63notes.html."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948236"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-015-0110-5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90257-T"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP). 859\u2013870","author":"Meka Raghu","unstructured":"Raghu Meka , Omer Reingold , Guy N. Rothblum , and Ron D. Rothblum . 2014. Fast Pseudorandomness for Independence and Load Balancing - (Extended Abstract) . In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP). 859\u2013870 . Raghu Meka, Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. 2014. Fast Pseudorandomness for Independence and Load Balancing - (Extended Abstract). In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP). 859\u2013870."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61440-0_149"},{"key":"e_1_3_2_1_35_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan . 1995. Randomized Algorithms . Cambridge University Press . Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/060658400"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220361"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716317"},{"key":"e_1_3_2_1_39_1","unstructured":"Geoff Pike and Jyrki Alakuijala. 2011. Introducing cityhash. https:\/\/opensource.googleblog.com\/2011\/04\/introducing-cityhash.html  Geoff Pike and Jyrki Alakuijala. 2011. Introducing cityhash. https:\/\/opensource.googleblog.com\/2011\/04\/introducing-cityhash.html"},{"key":"e_1_3_2_1_40_1","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 209\u2013228","author":"P\u01cetra\u015fcu Mihai","year":"2013","unstructured":"Mihai P\u01cetra\u015fcu and Mikkel Thorup . 2013 . Twisted Tabulation Hashing . In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 209\u2013228 . Mihai P\u01cetra\u015fcu and Mikkel Thorup. 2013. Twisted Tabulation Hashing. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 209\u2013228."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701386216"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.18"},{"key":"e_1_3_2_1_44_1","volume-title":"High Speed Hashing for Integers and Strings. ArXiv, abs\/1504.06804","author":"Thorup Mikkel","year":"2015","unstructured":"Mikkel Thorup . 2015. High Speed Hashing for Integers and Strings. ArXiv, abs\/1504.06804 ( 2015 ). Mikkel Thorup. 2015. High Speed Hashing for Integers and Strings. ArXiv, abs\/1504.06804 (2015)."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/100800774"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90033-7"},{"key":"e_1_3_2_1_47_1","volume-title":"A New Hashing Method with Application for Game Playing. Computer Sciences Department","author":"Zobrist Albert Lindsey","unstructured":"Albert Lindsey Zobrist . 1970. A New Hashing Method with Application for Game Playing. Computer Sciences Department , University of Wisconsin , Madison, Wisconsin . Albert Lindsey Zobrist. 1970. A New Hashing Method with Application for Game Playing. Computer Sciences Department, University of Wisconsin, Madison, Wisconsin."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384259","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":47,"alternative-id":["10.1145\/3357713.3384259","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384259","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}