Zombie Hashing: Reanimating Tombstones in a Graveyard

Summary: Zombie hashing deamortizes tombstone handling in linear probing, redistributing tombstones in windows. Ordered (compact) and unordered (vectorized) deliver asymptotically optimal deamortization with ~95% space, high throughput, and low latency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hc855690866652281
Venue: SIGMOD
Year: 2025
Pagerank: 5.1176637e-05
Overall Rank: 9,866 | 33.67%
DOI: 10.1145/3725424

Incoming Non-self Citations Over Time

Authors

1. Yuvaraj Chesetti (Northeastern University)
2. Benwei Shi (University of Utah)
3. Jeff M. Phillips (University of Utah)
4. Prashant Pandey (Northeastern University)

BibTeX Citation

@inproceedings{chesetti_sigmod25,
        title = {{Zombie Hashing: Reanimating Tombstones in a Graveyard}},
        author = {Chesetti, Yuvaraj and Shi, Benwei and Phillips, Jeff M. and Pandey, Prashant},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3725424},
        url = {https://dl.acm.org/doi/10.1145/3725424},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,623	Breadcrumb Filters: Fast Fully Featured Filters	2026	SIGMOD	4.9793485e-05
10,777	Succinct and Fast Tiny Pointer Hash Tables	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081992507
546	Faster: A Concurrent Key-Value Store with In-Place Updates	2018	SIGMOD	0.00016590738
786	Cicada: Dependably Fast Multi-Core In-Memory Transactions	2017	SIGMOD	0.00013988699
1,283	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB	0.00011209209
2,029	Teseo and the Analysis of Structural Dynamic Graphs	2021	VLDB	9.1592382e-05
2,071	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	9.0866982e-05
2,369	BlueCache: A Scalable Distributed Flash-based Key-value Store	2017	VLDB	8.5618147e-05
6,441	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	5.7834762e-05
7,325	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.5522404e-05
7,760	IcebergHT: High Performance Hash Tables Through Stability and Low Associativity	2023	SIGMOD	5.457277e-05
12,062	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,814	Analyzing Vectorized Hash Tables Across CPU Architectures	2023	VLDB
2	3,236	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB
3	4,144	Memory-Contention Responsive Hash Joins	1994	VLDB
4	4,890	Can Learned Models Replace Hash Functions?	2023	VLDB
5	1,283	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB
6	9,155	Hashing in Practice, Analysis of Hashing and Universal Hashing	1988	SIGMOD
7	10,777	Succinct and Fast Tiny Pointer Hash Tables	2026	VLDB
8	7,760	IcebergHT: High Performance Hash Tables Through Stability and Low Associativity	2023	SIGMOD
9	2,862	Concurrency and Linear Hashing	1985	PODS
10	14,015	Cache-Oblivious Hashing	2010	PODS