US5809494A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for rapidly and efficiently hashing records of large databases
Assignee: APPLIED LANGUAGE TECHNOLOGIES
•
Filing: 1995-11-16
•
Granted: 1998-09-15
•
Expires: 2015-11-16
Abstract
Abstract A method for rapidly hashing records in a large database stored on a secondary storage device in which a set of memory-blocks are preferably established in main memory for receiving information. Each memory block is associated with a sub-range of hash values that collectively span a range of hash values derived from one or more fields of the database records. The hash values together with other information are distributed among the memory-blocks in accordance with the range of hash values. As each memory block fills, its contents are written to an intermediate file associated with the memory-block in secondary storage. The intermediate files are subsequently retrieved and the hash values stored therein are ordered. The ordered intermediate files are then written to secondary storage as a single hash table spanning the entire database.
Inventors
- 👤 John N. Nguyen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 20:23
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9014; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
226 words
A method for rapidly hashing records in a database stored on a secondary storage device, the size of said database exceeding that of a primary storage in which operations on said database are to be performed, comprising the steps of: A. providing in primary storage a set of memory-blocks for receiving hash records therein, each said memory-block being associated with a sub-range of hash values that collectively span a range of hash values encompassing said database; B. repeatedly retrieving from the secondary storage device groups of records and generating a hash value for each record; C. associating each hash value with at least secondary storage address information for the respective record so as to form retrieval information comprising intermediate hash records that characterize the retrieved records; D. distributing said retrieval information among said memory-blocks in accordance with the range of hash values associated with the respective records; E. as each memory-block fills, writing the corresponding intermediate hash records to an intermediate file associated with the memory block in secondary storage to enable further intermediate hash records to be distributed to said memory-block; F. retrieving said intermediate files from secondary storage and ordering the intermediate hash records therein so as to form hashed files; and G. writing the hashed files to secondary storage as a single composite file to form a hash table spanning the entire database.
Claim 2
Independent Claim
226 words
A method for rapidly hashing records in a database stored on a secondary storage device, the size of said database exceeding that of a primary storage in which operations on said database are to be performed, comprising the steps of: A. providing in primary storage a set of memory-blocks for receiving hash records therein, each said memory-block being associated with a sub-range of hash values that collectively span a range of hash values encompassing said database; B. repeatedly retrieving from the secondary storage device groups of records and generating a hash value for each record; C. associating each hash value with at least secondary storage address information for the respective record so as to form retrieval information comprising intermediate hash records that characterize the retrieved records; D. distributing said retrieval information among said memory-blocks in accordance with the range of hash values associated with the respective records; E. as each memory-block fills, writing the corresponding intermediate hash records to an intermediate file associated with the memory block in secondary storage to enable further intermediate hash records to be distributed to said memory-block; F. retrieving said intermediate files from secondary storage and ordering the intermediate hash records therein so as to form hashed files; and G. writing the hashed files to secondary storage as a single composite file to form a hash table spanning the entire database.
Claim 3
Dependent Claim
29 words
The method of claim 1 in which each said memory-block is associated with a distinct sub-range of locations in which the records of said database are to be stored.
Claim 4
Dependent Claim
33 words
The method of claim 2 in which each said memory-block is associated with a subrange of less than 10% of the locations in which the records of said database are to be stored.
Claim 5
Dependent Claim
33 words
The method of claim 2 in which each said memory-block is associated with a subrange of less than 2% of the locations in which the records of said database are to be stored.
Claim 6
Dependent Claim
21 words
The method of claim 2 in which each memory block occupies less than 10% of the available primary memory user space.
Claim 7
Dependent Claim
21 words
The method of claim 2 in which each memory block occupies less than 2% of the available primary memory user space.
Claim 8
Dependent Claim
38 words
The method of claim 1 in which each said memory block, on filling, is appended to an intermediate file corresponding to said block to thereby form an extended file for amalgamating the successive contents of the corresponding memory-block.
Claim 9
Dependent Claim
14 words
The method of claim 7 in which said records are hashed by hash number.
Claim 10
Dependent Claim
49 words
The method of claim 8 which includes the step of generating at least a second hash value for each record, said second hash value being used to define the location of the hash record within the memory-block to thereby specify the location of said hash records within said block.
References Cited (Backward Citations)
US4215402A
Cited
US4464713A
Cited
US4959785A
Cited
US4996663A
Cited
US5121495A
Cited
US4961139A
Cited
US5359720A
Cited
US5197002A
Cited
US5333313A
Cited
US5199073A
Cited
US5204958A
Cited
US5542087A
Cited
US5511190A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-14 | 2002-03-16 | 2002-09-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-14 | 2006-03-16 | 2006-09-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-14 | 2010-03-16 | 2010-09-15 | $7700.00 | Window Closed / Lapsed |