Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-09-26
1999-09-28
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707101, 707102, 707103, G06F 1730
Patent
active
059604344
ABSTRACT:
The present invention is a system, method, and computer program product for dynamically sizing a hash table when the average number of records per bucket in the hash table exceeds a maximum average number of records per bucket. In one embodiment, the hash table employs a modulo hashing function. In a second embodiment, the number of buckets is grown by a multiple of the previous number of buckets and records are re-hashed using a lazy re-hashing modulo algorithm that re-hashes records in a hash bucket only when those records are searched. In the second embodiment, when a hash table is re-sized, each new bucket is provided with a logical back pointer, or index, to a pre-existing bucket that potentially contains records that belong in the new bucket. When a search is directed at a new bucket, the logical back pointer, or index, directs the search to a pre-existing bucket. When a search of a pre-existing bucket finds a data record that belongs in a new bucket, the record is moved to the new bucket. When there are no more records in a pre-existing bucket that belong in a new bucket, the logical back pointer from the new bucket to the pre-existing bucket is removed. Preferably, the logical back pointer is stored in the bucket where a regular pointer would normally be stored so that no extra space is needed.
REFERENCES:
patent: 4996663 (1991-02-01), Nemes
patent: 5121495 (1992-06-01), Nemes
patent: 5197002 (1993-03-01), Spencer
patent: 5265245 (1993-11-01), Nordstrom et al.
patent: 5287499 (1994-02-01), Nemes
patent: 5511190 (1996-04-01), Sharma et al.
patent: 5612865 (1997-03-01), Dasgupta
patent: 5623545 (1997-04-01), Childs et al.
patent: 5706462 (1998-01-01), Matousek
Keller, Fast Rehashing in PRAM Emulations, IEEE, pp. 626-631, Dec. 1993.
Chung et al, Dynamic Signature Hashing, IEEE, pp. 257-262, Sep. 1989.
Black Thomas G.
Coby Frantz
Silicon Graphics Inc.
LandOfFree
System method and computer program product for dynamically sizin does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System method and computer program product for dynamically sizin, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System method and computer program product for dynamically sizin will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-716137