External Perfect Hashing

Summary: External perfect hashing for large external files enables single-disk retrieval of any record with a small in-core table. It analyzes tradeoffs between insertion cost and storage utilization under a policy to cap insertions, showing promising feasibility for external data management. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2335
Venue: SIGMOD
Year: 1985
Pagerank: 6.3458215e-05
Overall Rank: 5,150 | 64.67%
DOI: 10.1145/318898.318916

Incoming Non-self Citations Over Time

Authors

1. Per-Ake Larson (University of Waterloo)
2. M V Ramakrishna (University of Waterloo)

BibTeX Citation

@inproceedings{larson_sigmod85,
        title = {{External Perfect Hashing}},
        author = {Larson, Per-Ake and Ramakrishna, M V},
        series = {{SIGMOD} '85},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/318898.318916},
        url = {https://dl.acm.org/doi/10.1145/318898.318916},
        year = {1985}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,242	Analysis of Bounded Disorder file organization	1988	PODS	5.9425753e-05
13,087	Fast Search In Main Memory Databases	1992	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
14,525	External hashing with limited internal storage	1982	PODS	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,287	Is Perfect Hashing Practical for OLAP Systems?	2024	CIDR
2	1,206	Random Sampling from Hash Files	1990	SIGMOD
3	13,087	Fast Search In Main Memory Databases	1992	SIGMOD
4	13,703	Cache-Oblivious Hashing	2010	PODS
5	507	Interpolation-Based Index Maintenance	1983	PODS
6	5,577	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB
7	8,995	Hashing in Practice, Analysis of Hashing and Universal Hashing	1988	SIGMOD
8	3,848	A Single-File Version of Linear Hashing with Partial Expansions	1982	VLDB
9	13,242	A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table	1984	VLDB
10	14,525	External hashing with limited internal storage	1982	PODS