External hashing with limited internal storage

Summary: Derives information-theoretic lower bounds for bucket-size-1 and matching algorithms showing how minimal per-bucket bits can guarantee single-probe external hashing. Extends to general bucket sizes with variable/fixed-bit schemes and practical tradeoffs (e.g., 8 bits/bucket for b=50 at 0.95 load) to eliminate extra external probes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 634
Venue: PODS
Year: 1982
Pagerank: -
Overall Rank: 14,525 | 0.35%
DOI: 10.1145/588111.588153

Incoming Non-self Citations Over Time

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

Authors

1. Gaston H. Gonnet (University of Waterloo)
2. Per-Åke Larson (Åbo Akademi University)

BibTeX Citation

@inproceedings{gonnet_pods82,
        address = {New York, NY, USA},
        series = {{PODS} '82},
        title = {{External hashing with limited internal storage}},
        url = {https://dl.acm.org/doi/10.1145/588111.588153},
        doi = {10.1145/588111.588153},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gonnet, Gaston H. and Larson, Per-Åke},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,150	External Perfect Hashing	1985	SIGMOD	6.3458215e-05

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	8,880	Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity	2022	SIGMOD
2	3,848	A Single-File Version of Linear Hashing with Partial Expansions	1982	VLDB
3	507	Interpolation-Based Index Maintenance	1983	PODS
4	833	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS
5	1,206	Random Sampling from Hash Files	1990	SIGMOD
6	13,242	A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table	1984	VLDB
7	2,758	Unified Dynamic Hashing	1984	VLDB
8	8,995	Hashing in Practice, Analysis of Hashing and Universal Hashing	1988	SIGMOD
9	13,703	Cache-Oblivious Hashing	2010	PODS
10	5,150	External Perfect Hashing	1985	SIGMOD