Method and apparatus for testing membership in a set through hash coding with allowable errors
Number of patents in Portfolio can not be more than 2000
United States of America Patent
Stats
-
Sep 15, 1981
Grant Date -
N/A
app pub date -
Apr 2, 1979
filing date -
Apr 2, 1979
priority date (Note) -
Expired
status (Latency Note)
A preliminary load of PAIR data current through [] has been loaded. Any more recent PAIR data will be loaded within twenty-four hours. |
PAIR data current through []
A preliminary load of cached data will be loaded soon.
Any more recent PAIR data will be loaded within twenty-four hours.
Next PAIR Update Scheduled on [ ] |
Importance
US Family Size
|
Non-US Coverage
|
Patent Longevity
|
Forward Citations
|
Abstract
A machine-implemented process, and apparatus, for performing a set membership test on large sets through the technique of binary hash coding with a known allowable expectation of an error. The present invention does not employ content addressable memory; rather, the present invention performs set membership testing by utilizing a hash function, which produces a randomized plurality of simple address locations within a bulk memory, for each item in the set. A testing for membership comprises employing a logical AND operation upon all values of binary indicators at memory locations addressed by hash values of a test item, to determine whether each and every hash value generated for the test item exactly matches with previously loaded indicators at those address locations in the bulk memory, which in the pereferred embodiment is of the CCD type. The present invention is a machine-implemented process, and employs a known algorithm as part of the overall process. The present invention also essentially comprises synergistic interaction of a hardware item called a 'hash board', and a bulk memory. The hash board generates a large number of hash addresses for any given item, using minimal computation time. The expected error rate is a function of the vocabulary size and the total number of indicators in the bulk memory. The bulk memory allows a low error rate for large vocabularies without exceeding the statistically ideal loading density of 50 percent. The hashing technique, together with its hardware implementation, allows a black box approach to general set membership testing. Information stored in the bulk memory can be said to be encrypted because the randomizing process makes it impossible to retrieve the original set of items. A preferred embodiment of the machine-implemented process, and apparatus is for on-line spelling checking of each word which appears in daily newspaper production, against a selective 20,000-word vocabulary, previously stored as a randomized set of simple bit addresses.
First Claim
Family
- 15 United States
- 10 France
- 8 Japan
- 7 China
- 5 Korea
- 2 Other
Patent Owner(s)
- AMERICAN NEWSPAPER PUBLISHERS ASSOCIATION;NEWSPAPER ASSOCIATION OF AMERICA, INC.
International Classification(s)
Inventor(s)
Inventor Name | Address | # of filed Patents | Total Citations |
---|---|---|---|
Cheswick, William R | New Hope, PA | 3 | 136 |
Cichelli, Richard J | Allentown, PA | 2 | 582 |
Thompson, Michael Q | Bethlehem, PA | 9 | 270 |
Cited Art Landscape
- No Cited Art to Display
Patent Citation Ranking
Forward Cite Landscape
- No Forward Cites to Display
Maintenance Fees
Fee | Large entity fee | small entity fee | micro entity fee | due date |
---|
Fee | Large entity fee | small entity fee | micro entity fee |
---|---|---|---|
Surcharge after expiration - Late payment is unavoidable | $700.00 | $350.00 | $175.00 |
Surcharge after expiration - Late payment is unintentional | $1,640.00 | $820.00 | $410.00 |
Full Text
Legal Events
Matter Detail
Update Public Data Dismiss Edit SaveRenewals Detail
Edit SaveNote
The template below is formatted to ensure compatibility with our system.
Provide tags with | separated like (tags1|tags2).
Maximum length is 128 characters for Customer Application No
Mandatory Fields * - 'MatterType','AppType','Country','Title','SerialNo'.
Acceptable Date Format - 'MM/DD/YYYY'.
Acceptable Filing/App Types -
- Continuation/Divisional
- Original
- Paris Convention
- PCT National
- With Priority
- EP Validation
- Provisional Conversion
- Reissue
- Provisional
- Foreign Extension
Acceptable Status -
- Pending
- Abandoned
- Unfiled
- Expired
- Granted
Acceptable Matter Types -
- Patent
- Utility Model
- Supplemental Protection Certificate
- Design
- Inventor Certificate
- Plant
- Statutory Invention Reg
Advertisement
Advertisement
Advertisement
Recipient Email Address
Recipient Email Address
Comment
Recipient Email Address
Success
E-mail has been sent successfully.
Failure
Some error occured while sending email. Please check e-mail and try again!
PAIR load has been initiated
A preliminary load of cached data will be loaded soon. Current PAIR data will be loaded within twenty four hours.
File History PDF
Thank you for your purchase! The File Wrapper for Patent Number 4290105 will be available within the next 24 hours.
Add to Portfolio(s)
To add this patent to one, or more, of your portfolios, simply click the add button.
This Patent is in these Portfolios:
Add to additional portfolios:
Last Refreshed On:
Changes done successfully
Important Notes on Latency of Status data
Please note there is up to 60 days of latency in this Status indicator for certain status conditions. You can obtain up-to-date Status indicator readings by ordering PAIR for the file.
An application with the status "Published" (which means it is pending) may be recently abandoned, but not yet updated to reflect its abandoned status. However, an application filed less than one year ago is unlikely to be abandoned.
A patent with the status "Granted" may be recently expired, but not yet updated to reflect its expired status. However, it is highly unlikely a patent less than 3.5 years old would be expired.
An application with the status "Abandoned" is almost always current, but there is a small chance it was recently revived and the status not yet updated.
Important Note on Priority Date data
This priority date is an estimated earliest priority date and is purely an estimation. This date should not be taken as legal conclusion. No representations are made as to the accuracy of the date listed. Please consult a legal professional before relying on this date.
We are sorry but your current selection exceeds the maximum number of portfolios (0) for this membership level. Upgrade to our Level for up to -1 portfolios!.