Trie Hashing

Summary: Trie Hashing introduces an ordered, dynamic hashing scheme for disk-resident records. It supports high-insert workloads at ~70% load, with a search that completes in a single disk access for files with millions of records, unmatched by prior ordered-file hashers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2201
Venue: SIGMOD
Year: 1981
Pagerank: 0.00011605619
Overall Rank: 1,221 | 91.63%
DOI: 10.1145/582318.582322

Incoming Non-self Citations Over Time

Authors

1. Witold Litwin (INRIA)

BibTeX Citation

@inproceedings{litwin_sigmod81,
        title = {{Trie Hashing}},
        author = {Litwin, Witold},
        series = {{SIGMOD} '81},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582318.582322},
        url = {https://dl.acm.org/doi/10.1145/582318.582322},
        year = {1981}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,185	A Multikey Hashing Scheme Using Predicate Trees	1984	SIGMOD	6.3281371e-05
5,377	The Interpolation-Based Grid File	1985	PODS	6.2410452e-05
5,823	HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication	2020	VLDB	6.0752299e-05
6,242	Analysis of Bounded Disorder file organization	1988	PODS	5.9425753e-05
8,371	A Dynamic Hash File for Random and Sequential Accessing	1983	VLDB	5.4403607e-05
8,943	Compact O-Complete Trees	1988	VLDB	5.3483178e-05
13,239	Query Processing on Personal Computers: A Pragmatic Approach (Extended Abstract)	1984	VLDB	5.093636e-05
13,242	A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table	1984	VLDB	5.093636e-05
13,254	The Reconstruction and Optimization of Trie Hashing Functions	1983	VLDB	5.093636e-05
13,267	An Implementation of Impure Surrogates	1982	VLDB	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
2,961	Distribution-Dependent Hashing Functions and Their Characteristics	1975	SIGMOD	7.9173938e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,361	Cascade Hashing	1984	VLDB
2	5,185	A Multikey Hashing Scheme Using Predicate Trees	1984	SIGMOD
3	2,758	Unified Dynamic Hashing	1984	VLDB
4	13,087	Fast Search In Main Memory Databases	1992	SIGMOD
5	13,195	Order Preserving Linear Hashing Using Dynamic Key Statistics	1986	PODS
6	3,848	A Single-File Version of Linear Hashing with Partial Expansions	1982	VLDB
7	5,577	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB
8	4,357	Balanced Multidimensional Extendible Hash Tree	1986	PODS
9	507	Interpolation-Based Index Maintenance	1983	PODS
10	13,254	The Reconstruction and Optimization of Trie Hashing Functions	1983	VLDB