Method and system for data set storage by iteratively searching

Details Method and system for data set storage by iteratively searching Method and system for data set storage by iteratively searching

1994-10-26

1997-11-25

Black, Thomas G.

Coded data generation or conversion

Digital code to digital code converters

Tree structure

395602, 395603, 395617, 395800, 341 95, G06F 1730

Patent

active

056921772

ABSTRACT:
A storage and retrieval system for storage and retrieval of records in a computer system. In a preferred embodiment, the storage system generates various hashing functions, hashes the keys of the records to identify storage locations, and stores the records in the identified storage locations. The retrieval system retrieves a record for a key by using the hashing functions to identify a storage location and retrieving the data from the identified storage location. The storage system logically organizes storage (e.g., memory) into levels. Each level is further organized into bins, and each bin contains a fixed number of slots. Each slot contains storage for storing one record. The storage system preferably stores about half the records at the first level, a quarter of the records at the second level, and so on. The storage system uses hashing functions and hashes the keys to determine at which level, bin, and slot to store the record associated with the key. The storage system uses a tentative bin assignment hashing function to tentatively assign keys to bins. The storage system then searches for a perfect hashing function for assigning a subset of the tentatively assigned keys to slots within the bin. The storage system generates a definite bin assignment hashing function to identify the subset. The storage system generates a definite bin assignment hashing function and a perfect hashing function for each bin within each level. The retrieval system uses the tentative bin assignment hashing function, the definite bin assignment hashing functions, and the perfect hashing functions to locate records.

REFERENCES:
patent: 5087913 (1992-02-01), Eastman
patent: 5151697 (1992-09-01), Bunton
patent: 5265245 (1993-11-01), Nordstrom et al.
patent: 5390359 (1995-02-01), Damerau
Portice et al., "Perfect Hashing Functions for Hardware Applications", IEEE 1994.
Ramakrishna, "File Organization Using Composite Perfect Hashing", ACM Transactions on Database Systems, vol. 14, No. 2 Jun. 1989.
Lewis et al. "Hashing for dynamic and static internal tables." IEEE, pp. 45-56 Oct. 1988.
Dietzfelbinger et al. "Dynamic Perfect Hashing: Upper and Lower bounds." IEEE, pp. 524-530 1988.
M.V. Ramakrishna, Per-Ake Larson, "File Organization Using Composite Perfect Hashing," ACM Transactions on Database Systems, vol. 14, No. 2, pp. 231-263, Jun. 1989.
Andrew W. Appel, Guy J. Jacobson, "The World's Fastest Scrabble Program," Communications of the ACM, vol. 31, No. 5, pp. 572-585, May 1988.

Affiliated with

Also associated with

Rating

Method and system for data set storage by iteratively searching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for data set storage by iteratively searching , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for data set storage by iteratively searching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2116004