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)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,086 | External Perfect Hashing | 1985 | SIGMOD | 6.4608969e-05 |
Previous
Page 1 / 1
Next
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 |
|---|
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,720 | Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity | 2022 | SIGMOD | 4.4609699e-05 |
| 1,708 | A Single-File Version Of Linear Hashing With Partial Expansions | 1982 | VLDB | 0.00010815668 |
| 255 | Interpolation-Based Index Maintenance | 1983 | PODS | 0.00030498284 |
| 503 | Storage Mappings For Multidimensional Linear Dynamic Hashing | 1983 | PODS | 0.00021520176 |
| 783 | Random Sampling from Hash Files | 1990 | SIGMOD | 0.00016704834 |
| 13,043 | A Dynamic Perfect Hash Function Defined By An Extended Hash Indicator Table | 1984 | VLDB | 4.1945683e-05 |
| 1,723 | Unified Dynamic Hashing | 1984 | VLDB | 0.00010753629 |
| 8,820 | Hashing in Practice, Analysis of Hashing and Universal Hashing | 1988 | SIGMOD | 4.4419702e-05 |
| 13,504 | Cache-Oblivious Hashing | 2010 | PODS | - |
| 4,086 | External Perfect Hashing | 1985 | SIGMOD | 6.4608969e-05 |