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.2220529e-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,594	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.2421304e-05
3,261	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4807048e-05
3,454	Locating Data Sources in Large Distributed Systems	2003	VLDB	7.2857626e-05
4,164	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	6.7651384e-05
4,469	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.5834186e-05
7,469	LH*RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes	2000	SIGMOD	5.5174986e-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,863	Concurrency and Linear Hashing	1985	PODS	7.9276184e-05
5,060	Distributed Linear Hashing and Parallel Projection in Main Memory Databases	1990	VLDB	6.2912116e-05

Semantically Similar Papers

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