US5287499A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for information storage and retrieval utilizing a method of hashing and different collision avoidance schemes depending upon clustering in the hash table
Assignee: Nytell Software LLC
•
Filing: 1991-05-16
•
Granted: 1994-02-15
•
Expires: 2011-05-16
Abstract
Abstract An apparatus for performing storage and retrieval in an information storage system is disclosed which uses the hashing technique. In order to provide efficient and graceful operation under varying loading conditions, the system shifts between collision avoidance by linear probing with open addressing when the load is below a threshold, and collision avoidance by external chaining when the load is above a threshold. Insertion, deletion and retrieval operations are arranged to switch dynamically between the two collision avoidance stratagems as the local loading factor on the system, as measured by the number of records hashed to the same address, crosses preselected thresholds.
Inventors
- 👤 Richard M. Nemes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 20:27
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/0292; G06F16/00; G06F16/90; G06F16/901; G06F16/9014; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
107 words
An information storage and retrieval system for data records using a portion of each said data record for generating a hashed storage address in said system, said system comprising storage means for storing a collision count for each set of said data records having identical hashed storage addresses, first means responsive to said storage means for locally resolving collisions by open addressing when said collision count in said storage means is below a preselected threshold, and second means responsive to said storage means for locally resolving collisions by external chaining when said collision count in said storage means is equal to or greater than said preselected threshold.
Claim 2
Dependent Claim
107 words
An information storage and retrieval system for data records using a portion of each said data record for generating a hashed storage address in said system, said system comprising storage means for storing a collision count for each set of said data records having identical hashed storage addresses, first means responsive to said storage means for locally resolving collisions by open addressing when said collision count in said storage means is below a preselected threshold, and second means responsive to said storage means for locally resolving collisions by external chaining when said collision count in said storage means is equal to or greater than said preselected threshold.
Claim 3
Dependent Claim
34 words
The information storage and retrieval system according to claim 1 further comprising means for storing one of said data records at said hashed storage address when said collision count is below said preselected threshold.
Claim 4
Dependent Claim
43 words
The information storage and retrieval system according to claim 1 further comprising means for storing a pointer to one of said data records at said at said hashed storage address when said collision count is equal to or greater than said preselected threshold.
References Cited (Backward Citations)
US3704363A
Cited
US4339657A
Cited
US4380067A
Cited
US4638426A
Cited
US4680700A
Cited
US4564944A
Cited
US4680703A
Cited
US4695949A
Cited
US4764863A
Cited
US4663620A
Cited
US4922417A
Cited
US4996663A
Cited
US4866712A
Cited
US4961139A
Cited
US4979105A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-02-14 | 1997-08-16 | 1998-02-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-02-14 | 2001-08-16 | 2002-02-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-02-14 | 2005-08-16 | 2006-02-15 | $7700.00 | Window Closed / Lapsed |