ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

LH* - Linear Hashing for Distributed Files.

Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - Linear Hashing for Distributed Files. SIGMOD Conference 1993: 327-336
@inproceedings{DBLP:conf/sigmod/LitwinNS93,
  author    = {Witold Litwin and
               Marie-Anne Neimat and
               Donovan A. Schneider},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {LH* - Linear Hashing for Distributed Files},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {327-336},
  ee        = {http://doi.acm.org/10.1145/170035.170084, db/conf/sigmod/LitwinNS93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

LH* generalizes Linear Hsshing to parallel or distributed RAM and disk files. An LH* file can be created from objects provided by any number of distributed and autonomous clients. It can grow gracefully, one bucket at a time, to virtually any number of servers. The number of messages per insertion is one in general, and three in the worst case. The number of messages per retrieval is two in general, and four in the worst case. The load factor can be about constant, 65-95%, depending on the file parameters. The file can also support parallel operations. An LH* file can be much faster than a single site disk file, and/or can hold a much larger number of objects. It can be more efficient than any file with a centralized directory, or a static parallel or distributed hash file.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 BibTeX , SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1032 KB]

References

[ED88]
Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988) BibTeX
[Ell87]
Carla Schlatter Ellis: Concurrency in Linear Hashing. ACM Trans. Database Syst. 12(2): 195-217(1987) BibTeX
[Hac89]
Nabil I. Hachem, P. Bruce Berra: Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing. ICDE 1989: 305-312 BibTeX
[Kri86]
Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220 BibTeX
[Lar80]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[Lar88]
Per-Åke Larson: Dynamic Hash Tables. Commun. ACM 31(4): 446-457(1988) BibTeX
[Lit80]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[LNS93]
...
[LRLH91]
Witold Litwin, Nick Roussopoulos, Gérald Lévy, Wang Hong: Trie Hashing With Controlled Load. IEEE Trans. Software Eng. 17(7): 678-691(1991) BibTeX
[Ou91]
Seng Fuat Ou, Alan L. Tharp: High Storage Utilisation for Single-Probe Retrieval Linear Hashing. Comput. J. 34(5): 455-468(1991) BibTeX
[Sal88]
Betty Salzberg: File Structures: An Analytic Approach. Prentice-Hall 1988, ISBN 0-13-314550-6
BibTeX
[Sam89]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX
[Sch90]
...
[SPW90]
Charles Severance, Sakti Pramanik, P. Wolberg: Distributed Linear Hashing and Parallel Projection in Main Memory Databases. VLDB 1990: 674-682 BibTeX

Referenced by

  1. Witold Litwin, Thomas J. E. Schwarz: LH*RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes. SIGMOD Conference 2000: 237-248
  2. Haruo Yokota, Yasuhiko Kanemasa, Jun Miyazaki: Fat-Btree: An Update-Conscious Parallel Directory Structure. ICDE 1999: 448-457
  3. Peter Scheuermann, Gerhard Weikum, Peter Zabback: Data Partitioning and Load Balancing in Parallel Disk Systems. VLDB J. 7(1): 48-66(1998)
  4. Takahiro Hara, Kaname Harumoto, Masahiko Tsukamoto, Shojiro Nishio: Database Migration: A New Architecture for Transaction Processing in Broadband Networks. IEEE Trans. Knowl. Data Eng. 10(5): 839-854(1998)
  5. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - A Scalable, Distributed Data Structure. ACM Trans. Database Syst. 21(4): 480-525(1996)
  6. Ajit K. Patankar, Arie Segev, J. George Shanthikumar: A Directory Service for a Federation of CIM Databases with Migrating Objects. ICDE 1996: 142-150
  7. Jonas S. Karlsson, Witold Litwin, Tore Risch: LH*LH: A scalable High Performance Data Structure for Switched Multicomputers. EDBT 1996: 573-591
  8. Gerhard Weikum: Tutorial on Parallel Database Systems. ICDT 1995: 33-37
  9. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: RP*: A Family of Order Preserving Scalable Distributed Data Structures. VLDB 1994: 342-353
  10. Radek Vingralek, Yuri Breitbart, Gerhard Weikum: Distributed File Organization with Scalable Cost/Performance. SIGMOD Conference 1994: 253-264
  11. Brigitte Kröll, Peter Widmayer: Distributing a Search Tree Among a Growing Number of Processors. SIGMOD Conference 1994: 265-276
  12. X. Zhao, Roger G. Johnson, Nigel J. Martin: DBJ - A Dynamic Balancing Hash Join Algorithm in Multiprocessor Database Systems (Extented Abstract). EDBT 1994: 301-308
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:15 2009