{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:25Z","timestamp":1779174805065,"version":"3.51.4"},"reference-count":81,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:p>Hashing is a fundamental operation in database management, playing a key role in the implementation of numerous core database data structures and algorithms. Traditional hash functions aim to mimic a function that maps a key to a random value, which can result in collisions, where multiple keys are mapped to the same value. There are many well-known schemes like chaining, probing, and cuckoo hashing to handle collisions. In this work, we aim to study if using learned models instead of traditional hash functions can reduce collisions and whether such a reduction translates to improved performance, particularly for indexing and joins. We show that learned models reduce collisions in some cases, which depend on how the data is distributed. To evaluate the effectiveness of learned models as hash function, we test them with bucket chaining, linear probing, and cuckoo hash tables. We find that learned models can (1) yield a 1.4x lower probe latency, and (2) reduce the non-partitioned hash join runtime with 28% over the next best baseline for certain datasets. On the other hand, if the data distribution is not suitable, we either do not see gains or see worse performance. In summary, we find that learned models can indeed outperform hash functions, but only for certain data distributions.<\/jats:p>","DOI":"10.14778\/3570690.3570702","type":"journal-article","created":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T17:29:55Z","timestamp":1674494995000},"page":"532-545","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Can Learned Models Replace Hash Functions?"],"prefix":"10.14778","volume":"16","author":[{"given":"Ibrahim","family":"Sabek","sequence":"first","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kapil","family":"Vaidya","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Horn","sequence":"additional","affiliation":[{"name":"TUM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Kipf","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[{"name":"Harvard University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Kraska","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,1,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"International Journal of Computer Science Issues","author":"Alahmad Mohammad","year":"2013","unstructured":"Mohammad Alahmad and Imad Fakhri Taha Alshaikhli . Broad View of Cryptographic Hash Functions . International Journal of Computer Science Issues , 2013 . Mohammad Alahmad and Imad Fakhri Taha Alshaikhli. Broad View of Cryptographic Hash Functions. International Journal of Computer Science Issues, 2013."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113370"},{"key":"e_1_2_1_3_1","unstructured":"Austin Appleby. Murmurhash3 64-bit finalizer. https:\/\/code.google.com\/p\/smhasher\/wiki\/MurmurHash3. Austin Appleby. Murmurhash3 64-bit finalizer. https:\/\/code.google.com\/p\/smhasher\/wiki\/MurmurHash3."},{"key":"e_1_2_1_4_1","volume-title":"https:\/\/sites.google.com\/site\/murmurhash\/","author":"Appleby Austin","year":"2011","unstructured":"Austin Appleby . MurmurHash. https:\/\/sites.google.com\/site\/murmurhash\/ , 2011 . Austin Appleby. MurmurHash. https:\/\/sites.google.com\/site\/murmurhash\/, 2011."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ACM SIGMETRICS\/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems","author":"Atikoglu Berk","year":"2012","unstructured":"Berk Atikoglu , Yuehai Xu , Eitan Frachtenberg , Song Jiang , and Mike Paleczny . Workload Analysis of a Large-Scale Key-Value Store . In Proceedings of the ACM SIGMETRICS\/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems , 2012 . Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. Workload Analysis of a Large-Scale Key-Value Store. In Proceedings of the ACM SIGMETRICS\/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, 2012."},{"key":"e_1_2_1_6_1","first-page":"42","volume-title":"Annales des Sciences Naturelles","volume":"7","author":"Audouin Audouin","year":"1837","unstructured":"Audouin Audouin and Brongniart Brongniart . Annales des sciences naturelles-vol. 7 (series-2) . In Annales des Sciences Naturelles , volume 7 , pages 42 -- 110 . Crochard , 1837 . Audouin Audouin and Brongniart Brongniart. Annales des sciences naturelles-vol. 7 (series-2). In Annales des Sciences Naturelles, volume 7, pages 42--110. Crochard, 1837."},{"key":"e_1_2_1_7_1","volume-title":"SipHash: A Fast Short-Input PRF. In Progress in Cryptology - INDOCRYPT","author":"Aumasson Jean-Philippe","year":"2012","unstructured":"Jean-Philippe Aumasson and Daniel J . Bernstein . SipHash: A Fast Short-Input PRF. In Progress in Cryptology - INDOCRYPT , 2012 . Jean-Philippe Aumasson and Daniel J. Bernstein. SipHash: A Fast Short-Input PRF. In Progress in Cryptology - INDOCRYPT, 2012."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544839"},{"key":"e_1_2_1_9_1","volume-title":"EDBT","author":"Behrens Tobias","year":"2018","unstructured":"Tobias Behrens , Viktor Rosenfeld , Jonas Traub , Sebastian Bre\u00df , and Volker Markl . Efficient SIMD Vectorization for Hashing in OpenCL . In EDBT , 2018 . Tobias Behrens, Viktor Rosenfeld, Jonas Traub, Sebastian Bre\u00df, and Volker Markl. Efficient SIMD Vectorization for Hashing in OpenCL. In EDBT, 2018."},{"key":"e_1_2_1_10_1","volume-title":"Theory and practice of monotone minimal perfect hashing. Journal of Experimental Algorithmics (JEA), 16:3--1","author":"Belazzougui Djamal","year":"2008","unstructured":"Djamal Belazzougui , Paolo Boldi , Rasmus Pagh , and Sebastiano Vigna . Theory and practice of monotone minimal perfect hashing. Journal of Experimental Algorithmics (JEA), 16:3--1 , 2008 . Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. Theory and practice of monotone minimal perfect hashing. Journal of Experimental Algorithmics (JEA), 16:3--1, 2008."},{"key":"e_1_2_1_11_1","volume-title":"William Kuszmaul. Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering. In IEEE Symposium on Foundations of Computer Science","author":"Bender Michael A.","year":"2021","unstructured":"Michael A. Bender , Bradley C. Kuszmaul , and William Kuszmaul. Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering. In IEEE Symposium on Foundations of Computer Science , 2021 . Michael A. Bender, Bradley C. Kuszmaul, and William Kuszmaul. Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering. In IEEE Symposium on Foundations of Computer Science, 2021."},{"key":"e_1_2_1_12_1","volume-title":"SIGMOD","author":"Binna Robert","year":"2018","unstructured":"Robert Binna , Eva Zangerle , Martin Pichl , G\u00fcnther Specht , and Viktor Leis . HOT : A Height Optimized Trie Index for Main-Memory Database Systems . In SIGMOD , 2018 . Robert Binna, Eva Zangerle, Martin Pichl, G\u00fcnther Specht, and Viktor Leis. HOT: A Height Optimized Trie Index for Main-Memory Database Systems. In SIGMOD, 2018."},{"key":"e_1_2_1_13_1","volume-title":"Linker Throughput Improvement in Visual Studio","author":"Blog Team","year":"2019","unstructured":"C++ Team Blog . Linker Throughput Improvement in Visual Studio 2019 . https:\/\/devblogs.microsoft.com\/cppblog\/linker-throughput-improvement-in-visual-studio-2019\/, 2019. C++ Team Blog. Linker Throughput Improvement in Visual Studio 2019. https:\/\/devblogs.microsoft.com\/cppblog\/linker-throughput-improvement-in-visual-studio-2019\/, 2019."},{"key":"e_1_2_1_14_1","volume-title":"Nivio Ziviani. Simple and Space-Efficient Minimal Perfect Hash Functions. In Proceedings of the International Conference on Algorithms and Data Structures","author":"Botelho Fabiano C.","year":"2007","unstructured":"Fabiano C. Botelho , Rasmus Pagh , and Nivio Ziviani. Simple and Space-Efficient Minimal Perfect Hash Functions. In Proceedings of the International Conference on Algorithms and Data Structures , 2007 . Fabiano C. Botelho, Rasmus Pagh, and Nivio Ziviani. Simple and Space-Efficient Minimal Perfect Hash Functions. In Proceedings of the International Conference on Algorithms and Data Structures, 2007."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321532"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies","author":"Cao Zhichao","year":"2020","unstructured":"Zhichao Cao , Siying Dong , Sagar Vemuri , and David H. C. Du . Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook . In Proceedings of the USENIX Conference on File and Storage Technologies , 2020 . Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In Proceedings of the USENIX Conference on File and Storage Technologies, 2020."},{"key":"e_1_2_1_18_1","unstructured":"Yann Collet. xxHash repository. https:\/\/cyan4973.github.io\/xxHash\/. Yann Collet. xxHash repository. https:\/\/cyan4973.github.io\/xxHash\/."},{"key":"e_1_2_1_19_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2001","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . Introduction to Algorithms . The MIT Press , 2 nd edition, 2001 . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.","edition":"2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0873"},{"issue":"4","key":"e_1_2_1_21_1","first-page":"738","article-title":"Meyer auf der Heide, Hans Rohnert, and Robert E","volume":"23","author":"Dietzfelbinger Martin","year":"1994","unstructured":"Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert E . Tarjan. Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM J. Comput. , 23 ( 4 ): 738 -- 761 , 1994 . Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert E. Tarjan. Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM J. Comput., 23(4):738--761, 1994.","journal-title":"Tarjan. Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM J. Comput."},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/978-3-642-23719-5_52","volume-title":"Algorithms - ESA 2011 - 19th Annual European Symposium","author":"Dietzfelbinger Martin","year":"2011","unstructured":"Martin Dietzfelbinger , Michael Mitzenmacher , and Michael Rink . Cuckoo hashing with pages . In Camil Demetrescu and Magn\u00fas M. Halld\u00f3rsson, editors, Algorithms - ESA 2011 - 19th Annual European Symposium , Saarbr\u00fccken, Germany , September 5--9, 2011 . Proceedings, volume 6942 of Lecture Notes in Computer Science , pages 615 -- 627 . Springer , 2011. Martin Dietzfelbinger, Michael Mitzenmacher, and Michael Rink. Cuckoo hashing with pages. In Camil Demetrescu and Magn\u00fas M. Halld\u00f3rsson, editors, Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbr\u00fccken, Germany, September 5--9, 2011. Proceedings, volume 6942 of Lecture Notes in Computer Science, pages 615--627. Springer, 2011."},{"key":"e_1_2_1_23_1","volume-title":"Theortical Computer Science","author":"Dietzfelbinger Martin","year":"2007","unstructured":"Martin Dietzfelbinger and Christoph Weidling . Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins . In Theortical Computer Science , 2007 . Martin Dietzfelbinger and Christoph Weidling. Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins. In Theortical Computer Science, 2007."},{"key":"e_1_2_1_24_1","volume-title":"Tsunami: A Learned Multi-Dimensional Index for Correlated Data and Skewed Workloads. In Proc. VLDB Endow.","author":"Jialin","year":"2020","unstructured":"Jialin Ding et al . Tsunami: A Learned Multi-Dimensional Index for Correlated Data and Skewed Workloads. In Proc. VLDB Endow. , 2020 . Jialin Ding et al. Tsunami: A Learned Multi-Dimensional Index for Correlated Data and Skewed Workloads. In Proc. VLDB Endow., 2020."},{"key":"e_1_2_1_25_1","volume-title":"SIGMOD","author":"Ding Jialin","year":"2020","unstructured":"Jialin Ding , Umar Farooq Minhas Jia Yu , Chi Wang , Jaeyoung Do , Yinan Li , Hantian Zhang , Badrish Chandramouli , Johannes Gehrke , Donald Kossmann , David Lomet , and Tim Kraska . ALEX : An Updatable Adaptive Learned Index . In SIGMOD , 2020 . Jialin Ding, Umar Farooq Minhas Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David Lomet, and Tim Kraska. ALEX: An Updatable Adaptive Learned Index. In SIGMOD, 2020."},{"key":"e_1_2_1_26_1","volume-title":"SIGMOD","author":"Dursun Kayhan","year":"2017","unstructured":"Kayhan Dursun , Carsten Binnig , Ugur Cetintemel , and Tim Kraska . Revisiting Reuse in Main Memory Database Systems . In SIGMOD , 2017 . Kayhan Dursun, Carsten Binnig, Ugur Cetintemel, and Tim Kraska. Revisiting Reuse in Main Memory Database Systems. In SIGMOD, 2017."},{"key":"e_1_2_1_27_1","first-page":"9","article-title":"US Secure Hash Algorithm 1 (SHA1)","volume":"3174","author":"Eastlake D.","year":"2001","unstructured":"D. Eastlake and P. Jones . US Secure Hash Algorithm 1 (SHA1) . RFC 3174 , IETF, 9 2001 . D. Eastlake and P. Jones. US Secure Hash Algorithm 1 (SHA1). RFC 3174, IETF, 9 2001.","journal-title":"RFC"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.14"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2179"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science","author":"Fotakis Dimitris","year":"2003","unstructured":"Dimitris Fotakis , Rasmus Pagh , Peter Sanders , and Paul G. Spirakis . Space Efficient Hash Tables with Worst Case Constant Access Time . In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science , 2003 . Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul G. Spirakis. Space Efficient Hash Tables with Worst Case Constant Access Time. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science, 2003."},{"key":"e_1_2_1_32_1","volume-title":"Storing a sparse table with 0 (1) worst case access time. Journal of the ACM (JACM), 31(3):538--544","author":"Fredman Michael L","year":"1984","unstructured":"Michael L Fredman , J\u00e1nos Koml\u00f3s , and Endre Szemer\u00e9di . Storing a sparse table with 0 (1) worst case access time. Journal of the ACM (JACM), 31(3):538--544 , 1984 . Michael L Fredman, J\u00e1nos Koml\u00f3s, and Endre Szemer\u00e9di. Storing a sparse table with 0 (1) worst case access time. Journal of the ACM (JACM), 31(3):538--544, 1984."},{"key":"e_1_2_1_33_1","unstructured":"Shay Gueron. Intel Advanced Encryption Standard (AES) New Instructions Set. https:\/\/www.intel.com\/content\/dam\/doc\/white-paper\/advanced-encryption-standard-new-instructions-set-paper.pdf. Shay Gueron. Intel Advanced Encryption Standard (AES) New Instructions Set. https:\/\/www.intel.com\/content\/dam\/doc\/white-paper\/advanced-encryption-standard-new-instructions-set-paper.pdf."},{"key":"e_1_2_1_34_1","volume-title":"Advances in Databases and Information Systems","author":"Gurumurthy Bala","year":"2018","unstructured":"Bala Gurumurthy , David Broneske , Marcus Pinnecke , Gabriel Campero Durand , and Gunter Saake . SIMD Vectorized Hashing for Grouped Aggregation . In Advances in Databases and Information Systems , 2018 . Bala Gurumurthy, David Broneske, Marcus Pinnecke, Gabriel Campero Durand, and Gunter Saake. SIMD Vectorized Hashing for Grouped Aggregation. In Advances in Databases and Information Systems, 2018."},{"key":"e_1_2_1_35_1","first-page":"317","volume-title":"Annual Symposium on Theoretical Aspects of Computer Science","author":"Hagerup Torben","year":"2001","unstructured":"Torben Hagerup and Torsten Tholey . Efficient minimal perfect hashing in nearly minimal space . In Annual Symposium on Theoretical Aspects of Computer Science , pages 317 -- 326 . Springer , 2001 . Torben Hagerup and Torsten Tholey. Efficient minimal perfect hashing in nearly minimal space. In Annual Symposium on Theoretical Aspects of Computer Science, pages 317--326. Springer, 2001."},{"key":"e_1_2_1_36_1","volume-title":"SIGMOD","author":"Hentschel Brian","year":"2022","unstructured":"Brian Hentschel , Utku Sirin , and Stratos Idreos . Entropy-Learned Hashing : 10x Faster Hashing with Controllable Uniformity . In SIGMOD , 2022 . Brian Hentschel, Utku Sirin, and Stratos Idreos. Entropy-Learned Hashing: 10x Faster Hashing with Controllable Uniformity. In SIGMOD, 2022."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236216"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424577"},{"key":"e_1_2_1_39_1","volume-title":"CIDR","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf , Thomas Kipf , Bernhard Radke , Viktor Leis , Peter A. Boncz , and Alfons Kemper . Learned Cardinalities : Estimating Correlated Joins with Deep Learning . In CIDR , 2019 . Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR, 2019."},{"key":"e_1_2_1_40_1","volume-title":"Thomas Neumann. RadixSpline: A Single-Pass Learned Index. In Proc. of aiDM@SIGMOD","author":"Kipf Andreas","year":"2020","unstructured":"Andreas Kipf , Ryan Marcus , Alexander van Renen , Mihail Stoian , Alfons Kemper , Tim Kraska , and Thomas Neumann. RadixSpline: A Single-Pass Learned Index. In Proc. of aiDM@SIGMOD , 2020 . Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. RadixSpline: A Single-Pass Learned Index. In Proc. of aiDM@SIGMOD, 2020."},{"key":"e_1_2_1_41_1","volume-title":"Probability and stochastic processes with applications. Havard Web-Based, page 5","author":"Knill Oliver","year":"1994","unstructured":"Oliver Knill . Probability and stochastic processes with applications. Havard Web-Based, page 5 , 1994 . Oliver Knill. Probability and stochastic processes with applications. Havard Web-Based, page 5, 1994."},{"key":"e_1_2_1_42_1","volume-title":"USA","author":"Knuth Donald E.","year":"1998","unstructured":"Donald E. Knuth . The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc ., USA , 1998 . Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., USA, 1998."},{"key":"e_1_2_1_43_1","volume-title":"Jeffrey Dean, and Neoklis Polyzotis. The Case for Learned Index Structures. In SIGMOD, page 489--504","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska , Alex Beutel , Ed H. Chi , Jeffrey Dean, and Neoklis Polyzotis. The Case for Learned Index Structures. In SIGMOD, page 489--504 , 2018 . Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The Case for Learned Index Structures. In SIGMOD, page 489--504, 2018."},{"key":"e_1_2_1_44_1","volume-title":"IMDM","author":"Lang Harald","year":"2015","unstructured":"Harald Lang , Viktor Leis , Martina-Cezara Albutiu , Thomas Neumann , and Alfons Kemper . Massively Parallel NUMA-Aware Hash Joins. In In-Memory Data Management and Analysis , IMDM , 2015 . Harald Lang, Viktor Leis, Martina-Cezara Albutiu, Thomas Neumann, and Alfons Kemper. Massively Parallel NUMA-Aware Hash Joins. In In-Memory Data Management and Analysis, IMDM, 2015."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141926"},{"key":"e_1_2_1_46_1","volume-title":"ICDE","author":"Leis Viktor","year":"2013","unstructured":"Viktor Leis , Alfons Kemper , and Thomas Neumann . The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases . In ICDE , 2013 . Viktor Leis, Alfons Kemper, and Thomas Neumann. The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. In ICDE, 2013."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s13389-015-0110-5","volume":"6","author":"Lemire Daniel","year":"2015","unstructured":"Daniel Lemire and Owen Kaser . Faster 64-bit Universal Hashing Using Carry-less Multiplications. Journal of Cryptographic Engineering , 6 : 171 -- 185 , 2015 . Daniel Lemire and Owen Kaser. Faster 64-bit Universal Hashing Using Carry-less Multiplications. Journal of Cryptographic Engineering, 6:171--185, 2015.","journal-title":"Journal of Cryptographic Engineering"},{"issue":"1","key":"e_1_2_1_48_1","article-title":"Data-Parallel Hashing Techniques for GPU Architectures","volume":"31","author":"Lessley Brenton","year":"2020","unstructured":"Brenton Lessley and Hank Childs . Data-Parallel Hashing Techniques for GPU Architectures . IEEE Transactions on Parallel and Distributed Systems , 31 ( 1 ), 2020 . Brenton Lessley and Hank Childs. Data-Parallel Hashing Techniques for GPU Architectures. IEEE Transactions on Parallel and Distributed Systems, 31(1), 2020.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_1_50_1","volume-title":"https:\/\/github.com\/viktorleis\/perfevent","author":"Library PerfEvent","year":"2019","unstructured":"PerfEvent Library . PerfEvent Library . https:\/\/github.com\/viktorleis\/perfevent , 2019 . PerfEvent Library. PerfEvent Library. https:\/\/github.com\/viktorleis\/perfevent, 2019."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.6.547"},{"key":"e_1_2_1_52_1","volume-title":"Tim Kraska. Benchmarking Learned Indexes. In Proc. VLDB Endow.","author":"Marcus Ryan","year":"2020","unstructured":"Ryan Marcus , Andreas Kipf , Alexander van Renen , Mihail Stoian , Sanchit Misra , Alfons Kemper , Thomas Neumann , and Tim Kraska. Benchmarking Learned Indexes. In Proc. VLDB Endow. , 2020 . Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, and Tim Kraska. Benchmarking Learned Indexes. In Proc. VLDB Endow., 2020."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452838"},{"key":"e_1_2_1_54_1","volume-title":"Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis","author":"Mitzenmacher Michael","year":"2017","unstructured":"Michael Mitzenmacher and Eli Upfal . Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis . Cambridge university press , 2017 . Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017."},{"issue":"22","key":"e_1_2_1_55_1","doi-asserted-by":"crossref","first-page":"3492","DOI":"10.1093\/bioinformatics\/btw397","volume":"32","author":"Mohamadi Hamid","year":"2016","unstructured":"Hamid Mohamadi , Justin Chu , Benjamin P. Vandervalk , and Inanc Birol . ntHash : Recursive Nucleotide Hashing. Bioinformatics , 32 ( 22 ): 3492 -- 3494 , 2016 . Hamid Mohamadi, Justin Chu, Benjamin P. Vandervalk, and Inanc Birol. ntHash: Recursive Nucleotide Hashing. Bioinformatics, 32(22):3492--3494, 2016.","journal-title":"Recursive Nucleotide Hashing. Bioinformatics"},{"issue":"1","key":"e_1_2_1_56_1","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1002\/rsa.20061","article-title":"Cores in random hypergraphs and boolean formulas","volume":"27","author":"Molloy Michael","year":"2005","unstructured":"Michael Molloy . Cores in random hypergraphs and boolean formulas . Random Structures & Algorithms , 27 ( 1 ): 124 -- 135 , 2005 . Michael Molloy. Cores in random hypergraphs and boolean formulas. Random Structures & Algorithms, 27(1):124--135, 2005.","journal-title":"Random Structures & Algorithms"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_58_1","first-page":"126","volume-title":"25th British National Conference on Databases, BNCOD '08","author":"Neumann Thomas","year":"2008","unstructured":"Thomas Neumann and Sebastian Michel . Smooth interpolating histograms with error guarantees. In Sharing Data, Information and Knowledge , 25th British National Conference on Databases, BNCOD '08 , pages 126 -- 138 , 2008 . Thomas Neumann and Sebastian Michel. Smooth interpolating histograms with error guarantees. In Sharing Data, Information and Knowledge, 25th British National Conference on Databases, BNCOD '08, pages 126--138, 2008."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/060658400"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_61_1","volume-title":"Palit and Kevin A. Wortman. Perfect Tabular Hashing in Pseudolinear Time. In IEEE Annual Computing and Communication Workshop and Conference (CCWC)","author":"Shekhar","year":"2021","unstructured":"Shekhar Palit and Kevin A. Wortman. Perfect Tabular Hashing in Pseudolinear Time. In IEEE Annual Computing and Communication Workshop and Conference (CCWC) , 2021 . Shekhar Palit and Kevin A. Wortman. Perfect Tabular Hashing in Pseudolinear Time. In IEEE Annual Computing and Communication Workshop and Conference (CCWC), 2021."},{"key":"e_1_2_1_62_1","volume-title":"Alfons Kemper. The Case for Learned Spatial Indexes. In Proceedings of the AIDB Workshop @VLDB","author":"Pandey Varun","year":"2020","unstructured":"Varun Pandey , Alexander van Renen , Andreas Kipf , Ibrahim Sabek , Jialin Ding , and Alfons Kemper. The Case for Learned Spatial Indexes. In Proceedings of the AIDB Workshop @VLDB , 2020 . Varun Pandey, Alexander van Renen, Andreas Kipf, Ibrahim Sabek, Jialin Ding, and Alfons Kemper. The Case for Learned Spatial Indexes. In Proceedings of the AIDB Workshop @VLDB, 2020."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610522"},{"issue":"3","key":"e_1_2_1_64_1","article-title":"The Power of Simple Tabulation Hashing","volume":"59","author":"Pundefinedtra\u015fcu Mihai","year":"2012","unstructured":"Mihai Pundefinedtra\u015fcu and Mikkel Thorup . The Power of Simple Tabulation Hashing . Journal of the ACM , 59 ( 3 ), 2012 . Mihai Pundefinedtra\u015fcu and Mikkel Thorup. The Power of Simple Tabulation Hashing. Journal of the ACM, 59(3), 2012.","journal-title":"Journal of the ACM"},{"key":"e_1_2_1_65_1","volume-title":"VLDB","author":"Qi Jianzhong","year":"2020","unstructured":"Jianzhong Qi , Guanli Liu , Christian S. Jensen , and Lars Kulik . Effectively Learning Spatial Indices . In VLDB , 2020 . Jianzhong Qi, Guanli Liu, Christian S. Jensen, and Lars Kulik. Effectively Learning Spatial Indices. In VLDB, 2020."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850585"},{"key":"e_1_2_1_67_1","first-page":"1","volume":"1321","author":"Rivest Ronald L.","year":"1992","unstructured":"Ronald L. Rivest . The MD5 Message-Digest Algorithm . RFC , 1321 : 1 -- 21 , 1992 . Ronald L. Rivest. The MD5 Message-Digest Algorithm. RFC, 1321:1--21, 1992.","journal-title":"RFC"},{"key":"e_1_2_1_68_1","unstructured":"J. Andrew Rogers. AquaHash. https:\/\/github.com\/jandrewrogers\/AquaHash\/. J. Andrew Rogers. AquaHash. https:\/\/github.com\/jandrewrogers\/AquaHash\/."},{"key":"e_1_2_1_69_1","volume-title":"SIGMOD, page 1228--1242","author":"Sabek Ibrahim","year":"2022","unstructured":"Ibrahim Sabek , Tenzin Samten Ukyab, and Tim Kraska. LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems . In SIGMOD, page 1228--1242 , 2022 . Ibrahim Sabek, Tenzin Samten Ukyab, and Tim Kraska. LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems. In SIGMOD, page 1228--1242, 2022."},{"key":"e_1_2_1_70_1","volume-title":"Proceedings of the AIDB Workshop @VLDB","author":"Sabek Ibrahim","year":"2021","unstructured":"Ibrahim Sabek , Kapil Vaidya , Dominik Horn , Andreas Kipf , and Tim Kraska . When Are Learned Models Better Than Hash Functions? In Proceedings of the AIDB Workshop @VLDB , 2021 . Ibrahim Sabek, Kapil Vaidya, Dominik Horn, Andreas Kipf, and Tim Kraska. When Are Learned Models Better Than Hash Functions? In Proceedings of the AIDB Workshop @VLDB, 2021."},{"key":"e_1_2_1_71_1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/978-1-4615-0005-6_8","volume-title":"Handbook of massive data sets","author":"Salomon David","year":"2002","unstructured":"David Salomon . Data compression . In Handbook of massive data sets , pages 245 -- 309 . Springer , 2002 . David Salomon. Data compression. In Handbook of massive data sets, pages 245--309. Springer, 2002."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882917"},{"key":"e_1_2_1_73_1","volume-title":"DK Panda. SimdHT-Bench: Characterizing SIMD-Aware Hash Table Designs on Emerging CPU Architectures. In IEEE International Symposium on Workload Characterization, IISWC","author":"Shankar Dipti","year":"2019","unstructured":"Dipti Shankar , Xiaoyi Lu , and Dhabaleswar K . DK Panda. SimdHT-Bench: Characterizing SIMD-Aware Hash Table Designs on Emerging CPU Architectures. In IEEE International Symposium on Workload Characterization, IISWC , 2019 . Dipti Shankar, Xiaoyi Lu, and Dhabaleswar K. DK Panda. SimdHT-Bench: Characterizing SIMD-Aware Hash Table Designs on Emerging CPU Architectures. In IEEE International Symposium on Workload Characterization, IISWC, 2019."},{"key":"e_1_2_1_74_1","unstructured":"Malte Skarupke. Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo). https:\/\/probablydance.com\/2018\/06\/16\/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo\/. Malte Skarupke. Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo). https:\/\/probablydance.com\/2018\/06\/16\/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo\/."},{"key":"e_1_2_1_75_1","article-title":"On the theory of diophantine approximations. i 1 (on a problem of a. ostrowski)","author":"S\u00f3s Vera T","year":"1957","unstructured":"Vera T S\u00f3s . On the theory of diophantine approximations. i 1 (on a problem of a. ostrowski) . Acta Mathematica Hungarica, 8(3--4):461--472 , 1957 . Vera T S\u00f3s. On the theory of diophantine approximations. i 1 (on a problem of a. ostrowski). Acta Mathematica Hungarica, 8(3--4):461--472, 1957.","journal-title":"Acta Mathematica Hungarica, 8(3--4):461--472"},{"key":"e_1_2_1_76_1","volume-title":"Tim Kraska. Bounding the Last Mile: Efficient Learned String Indexing. In Proceedings of the AIDB Workshop @VLDB","author":"Spector Benjamin","year":"2021","unstructured":"Benjamin Spector , Andreas Kipf , Kapil Vaidya , Chi Wang , Umar Farooq Minhas , and Tim Kraska. Bounding the Last Mile: Efficient Learned String Indexing. In Proceedings of the AIDB Workshop @VLDB , 2021 . Benjamin Spector, Andreas Kipf, Kapil Vaidya, Chi Wang, Umar Farooq Minhas, and Tim Kraska. Bounding the Last Mile: Efficient Learned String Indexing. In Proceedings of the AIDB Workshop @VLDB, 2021."},{"key":"e_1_2_1_77_1","volume-title":"Koji Toyota. Birthday Paradox for Multi-Collisions. In Proceedings of the International Conference on Information Security and Cryptology","author":"Suzuki Kazuhiro","year":"2006","unstructured":"Kazuhiro Suzuki , Dongvu Tonien , Kaoru Kurosawa , and Koji Toyota. Birthday Paradox for Multi-Collisions. In Proceedings of the International Conference on Information Security and Cryptology , 2006 . Kazuhiro Suzuki, Dongvu Tonien, Kaoru Kurosawa, and Koji Toyota. Birthday Paradox for Multi-Collisions. In Proceedings of the International Conference on Information Security and Cryptology, 2006."},{"key":"e_1_2_1_78_1","author":"Tch\u00f3rzewski Jacek","year":"2019","unstructured":"Jacek Tch\u00f3rzewski and Agnieszka Jak\u00f3bik . Theoretical and Experimental Analysis of Cryptographic Hash Functions . Journal of Telecommunications and Information Technology , 2019 . Jacek Tch\u00f3rzewski and Agnieszka Jak\u00f3bik. Theoretical and Experimental Analysis of Cryptographic Hash Functions. Journal of Telecommunications and Information Technology, 2019.","journal-title":"Journal of Telecommunications and Information Technology"},{"key":"e_1_2_1_79_1","volume-title":"ICDE","author":"Teubner Jens","year":"2013","unstructured":"Jens Teubner , Gustavo Alonso , Cagri Balkesen , and M. Tamer Ozsu . Main-Memory Hash Joins on Multi-Core CPUs: Tuning to the Underlying Hardware . In ICDE , 2013 . Jens Teubner, Gustavo Alonso, Cagri Balkesen, and M. Tamer Ozsu. Main-Memory Hash Joins on Multi-Core CPUs: Tuning to the Underlying Hardware. In ICDE, 2013."},{"key":"e_1_2_1_80_1","unstructured":"Reini Urban. Smhasher. https:\/\/github.com\/rurban\/smhasher. Reini Urban. Smhasher. https:\/\/github.com\/rurban\/smhasher."},{"key":"e_1_2_1_81_1","volume-title":"SIGKDD","author":"Wu Yuhan","year":"2021","unstructured":"Yuhan Wu , Zirui Liu , Xiang Yu , Jie Gui , Haochen Gan , Yuhao Han , Tao Li , Ori Rottenstreich , and Tong Yang . MapEmbed : Perfect Hashing with High Load Factor and Fast Update . In SIGKDD , 2021 . Yuhan Wu, Zirui Liu, Xiang Yu, Jie Gui, Haochen Gan, Yuhao Han, Tao Li, Ori Rottenstreich, and Tong Yang. MapEmbed: Perfect Hashing with High Load Factor and Fast Update. In SIGKDD, 2021."},{"issue":"2","key":"e_1_2_1_82_1","doi-asserted-by":"crossref","first-page":"187","DOI":"10.4064\/fm-46-2-187-189","article-title":"On successive settings of an arc on the circumference of a circle","volume":"46","author":"\u015bwierczkowski S.","year":"1958","unstructured":"S. \u015bwierczkowski . On successive settings of an arc on the circumference of a circle . Fundamenta Mathematicae , 46 ( 2 ): 187 -- 189 , 1958 . S. \u015bwierczkowski. On successive settings of an arc on the circumference of a circle. Fundamenta Mathematicae, 46(2):187--189, 1958.","journal-title":"Fundamenta Mathematicae"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3570690.3570702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T01:29:35Z","timestamp":1679448575000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3570690.3570702"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11]]},"references-count":81,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["10.14778\/3570690.3570702"],"URL":"https:\/\/doi.org\/10.14778\/3570690.3570702","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,11]]},"assertion":[{"value":"2023-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}