Linear hashing for distributed records

Details Linear hashing for distributed records Linear hashing for distributed records

1993-10-15

1996-07-30

Black, Thomas G.

Boots, shoes, and leggings

3642824, 3642551, 364DIG1, G06F 1730

Patent

active

055420877

ABSTRACT:
A data processing method and apparatus, which generate a correct memory address from a character or digit string such as a record key value, and which is adapted for use in distributed or parallel processing architectures such as computer networks, multiprocessing systems, and the like. The invention provides a plurality of client data processors and a plurality of file servers, each server including at least a respective one memory location or "bucket". The method of the invention includes the following steps: generating the key value by means of any one of the client data processors; generating a first memory address from the key value, the first address identifying a first memory location; selecting from the plurality of servers a server that includes the first memory location; transmitting the key value from the one client to the server that includes the first memory location; and determining whether the first address is the correct address by means of the server. The method of the invention further provides that if the first address is not the correct address then the following steps are performed: generating a second memory address from the key value by means of the server, the second address identifying a second memory location; selecting from the plurality of servers another server, which includes the second memory location; transmitting the key value from the server that includes the first memory location to the other server, which includes the second memory location; determining whether the second address is the correct address by means of the other server; and generating a third memory address, which is the correct address, if neither the first or second addresses is the correct address. The present invention provides fast storage and subsequent searching and retrieval of data records in data processing applications such as database applications.

REFERENCES:
patent: 4871903 (1989-10-01), Carrell
patent: 4922417 (1990-05-01), Churm et al.
patent: 5006978 (1991-04-01), Neches
patent: 5032987 (1991-07-01), Broder et al.
patent: 5199073 (1993-03-01), Scott
patent: 5210824 (1993-05-01), Putz et al.
patent: 5210870 (1993-05-01), Baum et al.
patent: 5287498 (1994-02-01), Perelman et al.
patent: 5357630 (1994-10-01), Oprescu et al.
patent: 5379424 (1995-01-01), Morimoto et al.
"The Fastest LAN Alive", BYTE, Jun. 1992, pp. 70-74.
David DeWitt et al., "Parallel Database Systems: The Future of High Performance Database Systems", Communications of the ACM, Jun. 1992, vol. 3, No. 6, pp. 85-98.
J. Gallant, "FDDI Routers and Bridges Create Niche for Memories", EDN, Apr. 1992, pp. 61-68.
S. F. Ou et al, "High Storage Utilization for Single-Probe Retrieval Linear Hashing", Computer Journal, vol. 34, No. (5), Oct. 1991, pp. 455-468.
Witold A. Litwin et al., "Trie Hashing with Controlled Load", IEEE Trasaction on Software Engineering, vol. 17, No. 7, Jul. 1991, pp. 678-691.
M. Hsue et al., "Concurrent Operations in Linear Hashing", Information Sciences, vol. 51, No. 2, Jul. 1990, pp. 193-211.
C. Severance et al., "Distributed Linear Hashing and Parallel Projection in Main Memory Databases", Proceeding of the 16th VLDB Conference, Brisbane, Australia, 1990, pp. 674-682.
M. Ouksel et al., "Concurrency in Multidimensional Linear Hashing", Proceedings of the 3rd International Conference on Foundations of Data Organization and Algorithms, Springer-Verlag, Jun. 1989, pp. 233-240.
Nabil I. Hachem et al., "Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing", Fifth International Conference on Data Engineering, 1989, pp. 305-312.
R. J. Enbody et al., "Dynamic Hashing Schemes", ACM Computing Surveys, vol. 20, No. 2, Jun. 1988, pp. 85-113.
Per-Ake Larson, "Dynamic Hash Tables", Communications of the ACM, vol. 31, No. 4, Apr. 1988, pp. 446-457.
Carla S. Ellis, "Concurrency in Linear Hashing", ACM Transactions on Database Systems, vol. 12, No. 2, Jun. 1987, pp. 195-217.
Hans-Peter Kriegel et al., "Multidimensional Order Preserving Linear Hashing with Partial Expansions", International Conference on Database Theory, Springer-Verlag, Sep. 1986, pp. 203-220.
Witold Litwin, "Linear Hashing: A New Tool for File and Table Addressing", IEEE, 1980.
Per-Ake Larson, "Linear Hashing with Partial Expansions", IEEE, 1980.
Witold Litwin, "Virtual Hashing: A Dynamically Changing Hashing", IEEE 1978.
Edward M. Reingold, "Searching", Encyclopedia of Computer Science, Van Nostrand Reinhold, pp. 1185-1191.

Affiliated with

Also associated with

Rating

Linear hashing for distributed records does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Linear hashing for distributed records, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear hashing for distributed records will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1668107