Cache-Oblivious Hashing

Summary: Proposes a cache-oblivious hash table that can match cache-aware search cost t_q = 1 + 1/2^{Ω(b)} for external hashing, i.e., near-perfect single-access searches across all blockings. Achieves this only under two realistic but non-model assumptions—b a power of two and blocks aligned to b—otherwise the best possible is t_q = 1 + O(α/b), the same as linear probing. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1527
Venue: PODS
Year: 2010
Pagerank: -
Overall Rank: 13,703 | 5.99%
DOI: 10.1145/1807085.1807124

Incoming Non-self Citations Over Time

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

Authors

1. Rasmus Pagh (IT University of Copenhagen)
2. Zhewei Wei (Hong Kong University of Science and Technology)
3. Ke Yi (Hong Kong University of Science and Technology)
4. Qin Zhang (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{pagh_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Cache-Oblivious Hashing}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807124},
        doi = {10.1145/1807085.1807124},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Pagh, Rasmus and Wei, Zhewei and Yi, Ke and Zhang, Qin},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,780	Can Learned Models Replace Hash Functions?	2023	VLDB
2	7,792	Cache-Oblivious Query Processing	2007	CIDR
3	5,150	External Perfect Hashing	1985	SIGMOD
4	14,525	External hashing with limited internal storage	1982	PODS
5	13,087	Fast Search In Main Memory Databases	1992	SIGMOD
6	2,250	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD
7	8,995	Hashing in Practice, Analysis of Hashing and Universal Hashing	1988	SIGMOD
8	2,801	Concurrency and Linear Hashing	1985	PODS
9	1,278	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB
10	1,110	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB