{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:44:02Z","timestamp":1787017442160,"version":"build-2736575974"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62172390"],"award-info":[{"award-number":["62172390"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Hashing index is widely used to support efficient point operations. We observe that there is a conflict between performance and memory utilization goals. Existing hashing indices often have to trade off hash table access latency for better memory utilization. Moreover, many designs support only unique keys, and their performance is often suboptimal with skew workloads.<\/jats:p>\n                  <jats:p>In this paper, we propose Pea Hash with two techniques to address the above two problems: (i) adaptive hashing strategy that holistically optimizes both access latency and memory utilization, and (ii) data-aware adaptive buckets that accommodate unique keys, and keys with various numbers of duplicates. We develop both an NVM-optimized Pea Hash and a DRAM-based Pea Hash index. Experiments on a machine equipped with Intel Optane DC Persistent memory show that compared to state-of-the-art NVM-optimized hashing indices, the NVM-optimized Pea Hash achieves up to 13.8x performance improvements with similar memory utilization. The DRAM-based Pea Hash outperforms existing in-DRAM hashing index designs, showing the generality of the proposed techniques.<\/jats:p>","DOI":"10.1145\/3588962","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T13:42:05Z","timestamp":1685454125000},"page":"1-25","source":"Crossref","is-referenced-by-count":12,"title":["Pea Hash: A Performant Extendible Adaptive Hashing Index"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3897-1155","authenticated-orcid":false,"given":"Zhuoxuan","family":"Liu","sequence":"first","affiliation":[{"name":"SKLP and Center for Advanced Computer Systems, Institute of Computing Technology, CAS; University of Chinese Academy of Sciences, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1043-6236","authenticated-orcid":false,"given":"Shimin","family":"Chen","sequence":"additional","affiliation":[{"name":"SKLP and Center for Advanced Computer Systems, Institute of Computing Technology, CAS; University of Chinese Academy of Sciences, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463585.2463589"},{"key":"e_1_2_2_2_1","first-page":"553","article-title":"BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory","volume":"11","author":"Arulraj Joy","year":"2018","unstructured":"Joy Arulraj, Justin J. Levandoski, Umar Farooq Minhas, and Per-\u00c5ke Larson. 2018. BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory. PVLDB 11, 5 (2018), 553--565.","journal-title":"PVLDB"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732227"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461543"},{"key":"e_1_2_2_6_1","volume-title":"Dong Ping Zhang","author":"Breslow Alex D.","year":"2016","unstructured":"Alex D. Breslow, Dong Ping Zhang, Joseph L. Greathouse, Nuwan Jayasena, and Dean M. Tullsen. 2016. Horton Tables: Fast Hash Tables for In-Memory Data-Intensive Computing. In 2016 USENIX Annual Technical Conference, USENIX ATC 2016, Denver, CO, USA, June 22--24, 2016, Ajay Gulati and Hakim Weatherspoon (Eds.). USENIX Association, 281--294."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1116\/1.3301579"},{"key":"e_1_2_2_8_1","unstructured":"J. L. Carlson and S. Sanfilippo. 2013. Redis in action. Manning."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_2_2_10_1","volume-title":"26th Annual Symposium on Foundations of Computer Science","author":"Celis Pedro","year":"1985","unstructured":"Pedro Celis, Per-\u00c5ke Larson, and J. Ian Munro. 1985. Robin Hood Hashing (Preliminary Report). In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21--23 October 1985. 281--288."},{"key":"e_1_2_2_11_1","volume-title":"Rethinking Database Algorithms for Phase Change Memory. In CIDR 2011, Fifth Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 9--12, 2011, Online Proceedings. 21--31","author":"Chen Shimin","year":"2011","unstructured":"Shimin Chen, Phillip B. Gibbons, and Suman Nath. 2011. Rethinking Database Algorithms for Phase Change Memory. In CIDR 2011, Fifth Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 9--12, 2011, Online Proceedings. 21--31."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_2_2_13_1","volume-title":"A revolutionary breakthrough in memory technology. Intel 3D XPoint launch keynote","author":"Crooke Rob","year":"2015","unstructured":"Rob Crooke and Mark Durcan. 2015. A revolutionary breakthrough in memory technology. Intel 3D XPoint launch keynote (2015)."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694359"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2883591.2883597"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_2_2_17_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--9.","journal-title":"Computers and Automation"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320092"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2013","author":"Fan Bin","year":"2013","unstructured":"Bin Fan, David G. Andersen, and Michael Kaminsky. 2013. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2013, Lombard, IL, USA, April 2--5, 2013, Nick Feamster and Jeffrey C. Mogul (Eds.). USENIX Association, 371--384."},{"key":"e_1_2_2_20_1","unstructured":"Hector Garcia-Molina Jeffrey D. Ullman and Jennifer Widom. 2009. Database systems - the complete book (2. ed.). Pearson Education."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_2_22_1","volume-title":"Next generation databases: NoSQL, newSQL, and big data","author":"Harrison Guy","unstructured":"Guy Harrison. 2015. Next generation databases: NoSQL, newSQL, and big data. Apress."},{"key":"e_1_2_2_23_1","volume-title":"22nd International Symposium, DISC 2008, Arcachon, France, September 22--24, 2008. Proceedings (Lecture Notes in Computer Science","volume":"364","author":"Herlihy Maurice","year":"2008","unstructured":"Maurice Herlihy, Nir Shavit, and Moran Tzafrir. 2008. Hopscotch Hashing. In Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22--24, 2008. Proceedings (Lecture Notes in Computer Science, Vol. 5218), Gadi Taubenfeld (Ed.). Springer, 350--364."},{"key":"e_1_2_2_24_1","volume-title":"Halo: A Hybrid PMem-DRAM Persistent Hash Index with Fast Recovery. In SIGMOD '22: International Conference on Management of Data","author":"Hu Daokun","year":"2022","unstructured":"Daokun Hu, Zhiwen Chen, Wenkui Che, Jianhua Sun, and Hao Chen. 2022. Halo: A Hybrid PMem-DRAM Persistent Hash Index with Fast Recovery. In SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, Zachary Ives, Angela Bonifati, and Amr El Abbadi (Eds.). ACM, 1049--1063."},{"key":"e_1_2_2_25_1","volume-title":"Zixuan Wang, Yi Xu, Subramanya R Dulloor, et al.","author":"Izraelevitz Joseph","year":"2019","unstructured":"Joseph Izraelevitz, Jian Yang, Lu Zhang, Juno Kim, Xiao Liu, Amirsaman Memaripour, Yun Joon Soh, Zixuan Wang, Yi Xu, Subramanya R Dulloor, et al. 2019. Basic performance measurements of the intel optane DC persistent memory module. arXiv preprint arXiv:1903.05714 (2019)."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1958011"},{"key":"e_1_2_2_27_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_2_2_28_1","volume-title":"WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems. In 15th USENIX Conference on File and Storage Technologies, FAST 2017","author":"Lee Se Kwon","year":"2017","unstructured":"Se Kwon Lee, K. Hyun Lim, Hyunsub Song, Beomseok Nam, and Sam H. Noh. 2017. WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems. In 15th USENIX Conference on File and Storage Technologies, FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017. 257--270."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359635"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 12th International Conference on Very Large Data Bases (VLDB '86)","author":"Tobin","unstructured":"Tobin J. Lehman and Michael J. Carey. 1986. A Study of Index Structures for Main Memory Database Management Systems. In Proceedings of the 12th International Conference on Very Large Data Bases (VLDB '86). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 294--303."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-019-07277-8"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384355"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389134"},{"key":"e_1_2_2_34_1","volume-title":"ROART: Range-query Optimized Persistent ART. In 19th USENIX Conference on File and Storage Technologies, FAST 2021","author":"Ma Shaonan","year":"2021","unstructured":"Shaonan Ma, Kang Chen, Shimin Chen, Mengxing Liu, Jianglang Zhu, Hongbo Kang, and Yongwei Wu. 2021. ROART: Range-query Optimized Persistent ART. In 19th USENIX Conference on File and Storage Technologies, FAST 2021, February 23--25, 2021. 1--16."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/356643.356645"},{"key":"e_1_2_2_36_1","unstructured":"Memcached. 2018. Memcached. https:\/\/memcached.org\/."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3323298.3323302"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915251"},{"key":"e_1_2_2_39_1","volume-title":"9th Annual European Symposium","volume":"133","author":"Pagh Rasmus","year":"2001","unstructured":"Rasmus Pagh and Flemming Friche Rodler. 2001. Cuckoo Hashing. In Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28--31, 2001, Proceedings (Lecture Notes in Computer Science, Vol. 2161), Friedhelm Meyer auf der Heide (Ed.). Springer, 121--133."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070549"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.12.0130"},{"key":"e_1_2_2_42_1","volume-title":"Database management systems (3. ed.)","author":"Ramakrishnan Raghu","unstructured":"Raghu Ramakrishnan and Johannes Gehrke. 2003. Database management systems (3. ed.). McGraw-Hill."},{"key":"e_1_2_2_43_1","unstructured":"Redis. 2018. Redis. https:\/\/redis.io\/."},{"key":"e_1_2_2_44_1","volume-title":"Sadalage and Martin Fowler","author":"Pramod","year":"2012","unstructured":"Pramod J. Sadalage and Martin Fowler. 2012. NoSQL Distilled: A Brief Guide to the Emerging World of Polyglot Persistence. Addison-Wesley Professional."},{"key":"e_1_2_2_45_1","unstructured":"Stanford. 2022. Stanford Large Network Dataset Collection. https:\/\/snap.stanford.edu\/data\/."},{"key":"e_1_2_2_46_1","volume-title":"The missing memristor found. nature 453, 7191","author":"Strukov Dmitri B","year":"2008","unstructured":"Dmitri B Strukov, Gregory S Snider, Duncan R Stewart, and R Stanley Williams. 2008. The missing memristor found. nature 453, 7191 (2008), 80--83."},{"key":"e_1_2_2_47_1","volume-title":"SmartCuckoo: A Fast and Cost-Efficient Hashing Index Scheme for Cloud Storage Systems. In 2017 USENIX Annual Technical Conference, USENIX ATC 2017","author":"Sun Yuanyuan","year":"2017","unstructured":"Yuanyuan Sun, Yu Hua, Song Jiang, Qiuyu Li, Shunde Cao, and Pengfei Zuo. 2017. SmartCuckoo: A Fast and Cost-Efficient Hashing Index Scheme for Cloud Storage Systems. In 2017 USENIX Annual Technical Conference, USENIX ATC 2017, Santa Clara, CA, USA, July 12--14, 2017, Dilma Da Silva and Bryan Ford (Eds.). USENIX Association, 553--565."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2013.80"},{"key":"e_1_2_2_49_1","volume-title":"18th USENIX Conference on File and Storage Technologies, FAST 2020","author":"Yang Jian","year":"2020","unstructured":"Jian Yang, Juno Kim, Morteza Hoseinzadeh, Joseph Izraelevitz, and Steven Swanson. 2020. An Empirical Guide to the Behavior and Use of Scalable Persistent Memory. In 18th USENIX Conference on File and Storage Technologies, FAST 2020, Santa Clara, CA, USA, February 24--27, 2020. 169--182."},{"key":"e_1_2_2_50_1","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015","author":"Yang Jun","year":"2015","unstructured":"Jun Yang, Qingsong Wei, Cheng Chen, Chundong Wang, Khai Leong Yong, and Bingsheng He. 2015. NV-Tree: Reducing Consistency Cost for NVM-based Single Level Systems. In Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015, Santa Clara, CA, USA, February 16--19, 2015. 167--181."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2782251"},{"key":"e_1_2_2_52_1","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Zuo Pengfei","year":"2018","unstructured":"Pengfei Zuo, Yu Hua, and Jie Wu. 2018. Write-optimized and high-performance hashing index scheme for persistent memory. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). 461--476."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588962","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588962","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:47:38Z","timestamp":1750164458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588962"],"URL":"https:\/\/doi.org\/10.1145\/3588962","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}