LH*RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes

Summary: LH*RS is a high-availability, scalable SDDS that extends LH* with parity to tolerate k unavailable sites; k scales with file size. Parity uses Reed-Solomon codes, yielding minimal storage and access overhead while preserving LH*-level search performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3250
Venue: SIGMOD
Year: 2000
Pagerank: 5.6463718e-05
Overall Rank: 7,318 | 49.80%
DOI: 10.1145/342009.335418

Incoming Non-self Citations Over Time

Authors

1. Witold Litwin (University of Paris)
2. Thomas Schwarz, S.J. (Jesuit School of Theology)

BibTeX Citation

@inproceedings{litwin_sigmod00,
        title = {{LH*RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes}},
        author = {Litwin, Witold and Thomas Schwarz, S.J.},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335418},
        url = {https://dl.acm.org/doi/10.1145/342009.335418},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,558	Where in the World is My Data?	2011	VLDB	6.6328303e-05
12,779	LH*RS: A Highly Available Distributed Data Storage	2004	VLDB	5.093636e-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
3,465	LH* — Linear Hashing for Distributed Files	1993	SIGMOD	7.3910846e-05
4,374	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.7370696e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,904	RDSQ: Reliable Queue Protocol over Shared Logs	2018	SIGMOD
2	8,726	The LAW theorem: Local Reads and Linearizable Asynchronous Replication	2025	VLDB
3	4,374	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD
4	2,801	Concurrency and Linear Hashing	1985	PODS
5	4,932	Distributed Linear Hashing and Parallel Projection in Main Memory Databases	1990	VLDB
6	7,163	Resilient Logical Structures for Efficient Management of Replicated Data	1992	VLDB
7	4,003	XORing Elephants: Novel Erasure Codes for Big Data	2013	VLDB
8	3,465	LH* — Linear Hashing for Distributed Files	1993	SIGMOD
9	2,552	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB
10	12,779	LH*RS: A Highly Available Distributed Data Storage	2004	VLDB