{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:55:27Z","timestamp":1775638527954,"version":"3.50.1"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2339521, 2311954"],"award-info":[{"award-number":["2339521, 2311954"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    Linear probing-based hash tables offer high data locality and are considered among the fastest in real-world applications. However, they come with an inherent tradeoff between space efficiency and speed, i.e. when the hash table approaches full capacity, its performance tends to decline considerably due to an effect known as\n                    <jats:italic toggle=\"yes\">primary clustering.<\/jats:italic>\n                    As a result they are only used at low load factors.\n                  <\/jats:p>\n                  <jats:p>\n                    <jats:italic toggle=\"yes\">Tombstones<\/jats:italic>\n                    (markers for deleted elements) can help mitigate the effect of primary clustering in linear probing hash tables. However, tombstones require periodic redistribution, which, in turn, requires a complete halt of regular operations. This makes linear probing not suitable in practical applications where periodic halts are unacceptable.\n                  <\/jats:p>\n                  <jats:p>In this paper, we present a solution to forestall primary clustering in linear probing hash tables, ensuring high data locality and consistent performance even at high load factors. Our approach redistributes tombstones within small windows, deamortizing the cost of mitigating primary clustering and eliminating the need for periodic halts. We provide theoretical guarantees that our deamortization method is asymptotically optimal in efficiency and cost. We also design an efficient implementation within dominant linear-probing hash tables and show performance improvements.<\/jats:p>\n                  <jats:p>We introduce Zombie hashing in two variants: ordered (compact) and unordered (vectorized) linear probing hash tables. Both variants achieve consistent, high throughput and lowest variance in operation latency compared to other state-of-the-art hash tables across numerous churn cycles, while maintaining 95% space efficiency without downtime. Our results show that Zombie hashing overcomes the limitations of linear probing while preserving high data locality.<\/jats:p>","DOI":"10.1145\/3725424","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-27","source":"Crossref","is-referenced-by-count":2,"title":["Zombie Hashing: Reanimating Tombstones in Graveyard"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8573-4299","authenticated-orcid":false,"given":"Yuvaraj","family":"Chesetti","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8786-4009","authenticated-orcid":false,"given":"Benwei","family":"Shi","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1169-2965","authenticated-orcid":false,"given":"Jeff M.","family":"Phillips","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5576-0320","authenticated-orcid":false,"given":"Prashant","family":"Pandey","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807670"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3625817"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00115"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1089\/CMB.2015.0199"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196898"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694359"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602261"},{"key":"e_1_2_2_11_1","unstructured":"DynamoDB 2024. https:\/\/aws.amazon.com\/dynamodb\/. Accessed: 2024--10-06."},{"key":"e_1_2_2_12_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. https:\/\/www.usenix.org\/conference\/nsdi13\/technical-sessions\/presentation\/fan"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.180602"},{"key":"e_1_2_2_14_1","unstructured":"Google. 2024. Abseil \/ Abseil Containers. https:\/\/abseil.io\/docs\/cpp\/guides\/container Last accessed 2024--10-06."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389739"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/COMJNL\/15.4.314"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975062.3"},{"key":"e_1_2_2_18_1","unstructured":"Olzhas Kaiyrakhmet Songyi Lee Beomseok Nam Sam H. Noh and Young-ri Choi. 2019. SLM-DB: Single-Level Key-Value Store with Persistent Memory. 191--205. https:\/\/www.usenix.org\/conference\/fast19\/presentation\/kaiyrakhmet"},{"key":"e_1_2_2_19_1","unstructured":"Don Knuth. 1963. Notes On ''Open'' Addressing."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1283920.1283929"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540708.2540748"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11036-023-02158-y"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447708"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064015"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441581"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3309206"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/BIOINFORMATICS\/BTR011"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.11.003"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977714.19"},{"key":"e_1_2_2_32_1","unstructured":"Memcached 2024. Memcached. https:\/\/memcached.org\/. Accessed: 2024--10-06."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3552326.3587457"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/070702278"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_2_37_1","volume-title":"Mantis: A fast, small, and exact large-scale sequence-search index. Cell systems 7, 2","author":"Pandey Prashant","year":"2018","unstructured":"Prashant Pandey, Fatemeh Almodaresi, Michael A Bender, Michael Ferdman, Rob Johnson, and Rob Patro. 2018. Mantis: A fast, small, and exact large-scale sequence-search index. Cell systems 7, 2 (2018), 201--207."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588727"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1093\/BIOINFORMATICS\/BTX261"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/BIOINFORMATICS\/BTX636"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-021-02442--8"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380598"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.18420\/BTW2019-04"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570750"},{"key":"e_1_2_2_46_1","unstructured":"Redis 2024. Redis. https:\/\/redis.io\/. Accessed: 2024--10-06."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850585"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/368637.368827"},{"key":"e_1_2_2_49_1","unstructured":"Malte Skarupke. 2017. I Wrote The Fastest Hashtable. https:\/\/probablydance.com\/2017\/02\/26\/i-wrote-the-fastest-hashtable\/. Accessed: 2025-01--22."},{"key":"e_1_2_2_50_1","unstructured":"Swiss Table Notes 2024. abseil \/ Swiss Tables Design Notes. https:\/\/abseil.io\/about\/design\/swisstables. Accessed: 2024--10-06."},{"key":"e_1_2_2_51_1","unstructured":"Sebastian Sylvan. 2013. Robin Hood Hashing should be your default Hash Table implementation. https:\/\/www.sebastiansylvan.com\/post\/robin-hood-hashing-should-be-your-default-hash-table-implementation\/. Accessed: 2025-01--22."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2015.2512589"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.11.001"},{"key":"e_1_2_2_54_1","volume-title":"Compilers Principles. Techniques, and Tools","author":"Aho A. V.","year":"1986","unstructured":"Aho A. V. 1986. Compilers Principles. Techniques, and Tools (1986). https:\/\/cir.nii.ac.jp\/crid\/1570572699852468736 Publisher: Addison-Wesley publishing company."},{"key":"e_1_2_2_55_1","unstructured":"Wikipedia. 2024. MurmurHash. https:\/\/en.wikipedia.org\/wiki\/MurmurHash. Accessed: 2024--10-06."},{"key":"e_1_2_2_56_1","unstructured":"Wikipedia. 2024. Streaming SIMD Extensions. https:\/\/en.wikipedia.org\/wiki\/Streaming_SIMD_Extensions Accessed 2024--10-06."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611502"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025113"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:57:26Z","timestamp":1774983446000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725424"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725424"],"URL":"https:\/\/doi.org\/10.1145\/3725424","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}