Method and apparatus for testing membership in a set through hash coding with allowable errors
US4290105A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 2, 1979 |
| Grant date | Sep 15, 1981 |
| Priority date | — |
| Expiry date | Apr 2, 1999 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F40/232
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 c…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.