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: h51c0d392d3f73207
Venue: SIGMOD
Year: 1993
Pagerank: 7.2254724e-05
Overall Rank: 3,534 | 76.25%
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,592	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.2460099e-05
3,260	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4842462e-05
3,454	Locating Data Sources in Large Distributed Systems	2003	VLDB	7.2892132e-05
4,163	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	6.7683361e-05
4,467	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.5865346e-05
7,465	LH*RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes	2000	SIGMOD	5.5201116e-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,862	Concurrency and Linear Hashing	1985	PODS	7.9313182e-05
5,056	Distributed Linear Hashing and Parallel Projection in Main Memory Databases	1990	VLDB	6.2941909e-05

Semantically Similar Papers

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