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: 7372
Venue: SIGMOD
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,799 | 25.91%
DOI: 10.1145/3725424

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

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 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,434	Breadcrumb Filters: Fast Fully Featured Filters	2026	SIGMOD	5.093636e-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.00083340894
614	Faster: A Concurrent Key-Value Store with In-Place Updates	2018	SIGMOD	0.00015720975
760	Cicada: Dependably Fast Multi-Core In-Memory Transactions	2017	SIGMOD	0.0001425909
1,278	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB	0.00011362007
2,043	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	9.2674387e-05
2,141	Teseo and the Analysis of Structural Dynamic Graphs	2021	VLDB	9.0978534e-05
2,457	BlueCache: A Scalable Distributed Flash-based Key-value Store	2017	VLDB	8.5515986e-05
6,349	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	5.9049304e-05
7,189	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.6775326e-05
7,638	IcebergHT: High Performance Hash Tables Through Stability and Low Associativity	2023	SIGMOD	5.5768492e-05
11,759	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,932	Distributed Linear Hashing and Parallel Projection in Main Memory Databases	1990	VLDB
2	8,443	Analyzing Vectorized Hash Tables Across CPU Architectures	2023	VLDB
3	3,389	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB
4	4,104	Memory-Contention Responsive Hash Joins	1994	VLDB
5	4,780	Can Learned Models Replace Hash Functions?	2023	VLDB
6	1,278	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB
7	8,995	Hashing in Practice, Analysis of Hashing and Universal Hashing	1988	SIGMOD
8	7,638	IcebergHT: High Performance Hash Tables Through Stability and Low Associativity	2023	SIGMOD
9	2,801	Concurrency and Linear Hashing	1985	PODS
10	13,703	Cache-Oblivious Hashing	2010	PODS