LH

1 June 1993

proceedings article
Published by Association for Computing Machinery (ACM)

Vol. 22 (2) , 327-336
https://doi.org/10.1145/170035.170084

Abstract

LH* generalizes Linear Hashing 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.

Keywords

This publication has 5 references indexed in Scilit:

Trie hashing with controlled load
IEEE Transactions on Software Engineering, 1991
High Storage Utilisation for Single-Probe Retrieval Linear Hashing
The Computer Journal, 1991
Dynamic hashing schemes
ACM Computing Surveys, 1988
Dynamic hash tables
Communications of the ACM, 1988
Concurrency in linear hashing
ACM Transactions on Database Systems, 1987