LH* — Linear Hashing for Distributed Files

Summary: LH* extends linear hashing to autonomous distributed RAM/disk files, scaling one bucket at a time across an evolving server set without centralized directories. It maintains 65–95% load with only 1 (3 worst-case) insertion and 2 (4 worst-case) retrieval messages. (summarized by gpt-5.6-luna on Jul 21 2026)

Paper ID: 2715
Venue: SIGMOD
Year: 1993
Pagerank: 7.3910846e-05
Overall Rank: 3,465 | 76.23%
DOI: 10.1145/170035.170084

Incoming Non-self Citations Over Time

Authors

1. Witold Litwin (Hewlett Packard Enterprise; Paris Dauphine University; University of California Berkeley)
2. Marie-Anne Neimat (Hewlett Packard Enterprise)
3. Donovan A. Schneider (Hewlett Packard Enterprise)

BibTeX Citation

@inproceedings{litwin_sigmod93,
        title = {{LH* — Linear Hashing for Distributed Files}},
        author = {Litwin, Witold and Neimat, Marie-Anne and Schneider, Donovan A.},
        series = {{SIGMOD} '93},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/170035.170084},
        url = {https://dl.acm.org/doi/10.1145/170035.170084},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,552	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.4284603e-05
3,187	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.6555242e-05
3,382	Locating Data Sources in Large Distributed Systems	2003	VLDB	7.4565087e-05
4,075	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	6.9224298e-05
4,374	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.7370696e-05
7,318	LH*RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes	2000	SIGMOD	5.6463718e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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,801	Concurrency and Linear Hashing	1985	PODS	8.1117099e-05
4,932	Distributed Linear Hashing and Parallel Projection in Main Memory Databases	1990	VLDB	6.4385884e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,961	Distribution-Dependent Hashing Functions and Their Characteristics	1975	SIGMOD
2	833	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS
3	13,242	A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table	1984	VLDB
4	8,371	A Dynamic Hash File for Random and Sequential Accessing	1983	VLDB
5	3,848	A Single-File Version of Linear Hashing with Partial Expansions	1982	VLDB
6	12,779	LH*RS: A Highly Available Distributed Data Storage	2004	VLDB
7	2,552	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB
8	4,932	Distributed Linear Hashing and Parallel Projection in Main Memory Databases	1990	VLDB
9	7,318	LH*RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes	2000	SIGMOD
10	2,801	Concurrency and Linear Hashing	1985	PODS