US5897637A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for rapidly identifying the existence and location of an item in a file
Assignee: Apple Inc
•
Filing: 1997-03-07
•
Granted: 1999-04-27
•
Expires: 2017-03-07
Abstract
Abstract A system and method for rapidly identifying the existence and location of an item in a file using an improved hash table architecture. A hash table is constructed having a plurality of hash buckets, each identified by a primary hash key. Each hash entry in each hash bucket contains a pointer to a record in a master file, as well as a secondary hash key independent of the primary hash key. A search for a particular item is performed by identifying the appropriate hash bucket by obtaining a primary hash key for the search term. Individual hash entries within the hash bucket are checked for matches by comparing the stored secondary keys with the secondary key for the search term. Potentially matching records can be identified or ruled out without necessitating repeated reads of the master file. The improved hash table system and method is employed in a contextual text searching application for determining the intersection of a text search with a hierarchical categorization scheme.
Inventors
- 👤 Ramanathan V. Guha
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 00:20
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9014; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99941; Y10S707/99942; Y10S707/99943
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
83 words
A system for rapidly identifying the existence of an item in a file, comprising: a master file for storing a plurality of items; and a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising: a pointer to an item in the master file, for identifying the location of the item; and a secondary hash key obtained by applying a secondary hash function.
Claim 2
Independent Claim
83 words
A system for rapidly identifying the existence of an item in a file, comprising: a master file for storing a plurality of items; and a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising: a pointer to an item in the master file, for identifying the location of the item; and a secondary hash key obtained by applying a secondary hash function.
Claim 3
Dependent Claim
134 words
The system of claim 1, further comprising: a search term input device for obtaining a search term; a primary hash function application module coupled to the search term input device, for applying a primary hash function to obtain a primary hash key for the search term; a secondary hash function application module coupled to the search term input device, for applying the secondary hash function to obtain a secondary hash key for the search term; and a hash key comparison module coupled to the hash table, for comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket; wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.
Claim 4
Dependent Claim
38 words
The system of claim 2, wherein the search term comprises a plurality of characters, and the primary hash function application module applies a primary hash function by performing successive exclusive-OR operations on successive characters of the search term.
Claim 5
Dependent Claim
44 words
The system of claim 2, wherein the search term comprises a plurality of segments, and the secondary hash function application module applies a secondary hash function by encoding each of at least one of the plurality of segments according to a predetermined encoding scheme.
Claim 6
Dependent Claim
60 words
The system of claim 2, further comprising: an item comparison module, coupled to the master file and to the hash table, for, responsive to the hash key comparison module indicating at least one hash entry having a matching secondary hash key, comparing the search term with an item in the master file identified by the pointer in the hash entry.
Claim 7
Dependent Claim
30 words
The system of claim 5, further comprising: an output device coupled to the item comparison module, for out-putting the results of the item comparison performed by the item comparison module.
Claim 8
Dependent Claim
31 words
The system of claim 6, wherein, responsive to the results of the item comparison indicating a match, the output device outputs the location of the matching item in the master file.
Claim 9
Dependent Claim
33 words
The system of claim 2, further comprising: an output device coupled to the hash key comparison module, for outputting the results of the hash key comparison performed by the hash key comparison module.
Claim 10
Dependent Claim
32 words
The system of claim 8, wherein the output device, responsive to the results of the hash key comparison indicating a match, outputs the location of the matching item in the master file.
Claim 11
Dependent Claim
31 words
The system of claim 1, wherein: the master file is implemented as a database in a computer system; and the hash table is implemented as a database in a computer system.
Claim 12
Dependent Claim
35 words
The system of claim 1, wherein: the master file stores a plurality of descriptors, each descriptor representing a document associated with a particular subject category; and the item represents a result of a text search.
Claim 13
Independent Claim
109 words
A method of identifying the existence of an item in a file, comprising: a) applying a primary hash function to obtain a primary hash key for a search term; b) identifying a hash bucket having a primary hash key corresponding to the obtained primary hash key, the hash bucket comprising at least one hash entry, each hash entry comprising a value and a secondary hash key; c) applying a secondary hash function to obtain a secondary hash key for the search term; and d) comparing the secondary hash key for the search term with the secondary hash key for at least one hash entry in the identified hash bucket.
Claim 14
Independent Claim
109 words
A method of identifying the existence of an item in a file, comprising: a) applying a primary hash function to obtain a primary hash key for a search term; b) identifying a hash bucket having a primary hash key corresponding to the obtained primary hash key, the hash bucket comprising at least one hash entry, each hash entry comprising a value and a secondary hash key; c) applying a secondary hash function to obtain a secondary hash key for the search term; and d) comparing the secondary hash key for the search term with the secondary hash key for at least one hash entry in the identified hash bucket.
Claim 15
Dependent Claim
13 words
The method of claim 12, further comprising: e) outputting the results of d).
Claim 16
Dependent Claim
65 words
The method of claim 12, wherein the value in each hash entry represents a pointer to a record location in a master file, the method further comprising: e) responsive to d) indicating at least one match, retrieving a record in the master file having a location corresponding to the value in the matching hash entry; and f) comparing the search term with the retrieved record.
Claim 17
Dependent Claim
21 words
The method of claim 14, further comprising: g) responsive to f) indicating a match, outputting the pointer for the matching record.
Claim 18
Dependent Claim
18 words
The method of claim 14, further comprising: g) responsive to f) indicating a match, outputting the matching record.
References Cited (Backward Citations)
GB2136612A
Cited
US4996663A
Cited
US5301337A
Cited
US5408652A
Cited
US5542087A
Cited
US5542089A
Cited
US5615341A
Cited
US5742811A
Cited
WO1997022069A1
Cited
US5724573A
Cited
US5754849A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-04-26 | 2002-10-26 | 2003-04-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-04-26 | 2006-10-26 | 2007-04-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-04-26 | 2010-10-26 | 2011-04-27 | $7700.00 | Window Closed / Lapsed |