Method and apparatus for testing membership in a set through has

Boots – shoes – and leggings

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

364900, G06F 700

Patent

active

042901057

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.

REFERENCES:
patent: 3259883 (1966-07-01), Rabinow et al.
patent: 3568156 (1971-03-01), Thompson
patent: 3651459 (1972-03-01), Hahn
patent: 3855576 (1974-12-01), Braun et al.
patent: 3925761 (1975-12-01), Chaires et al.
patent: 3947825 (1976-03-01), Cassada
patent: 3969698 (1976-07-01), Bollinger et al.
patent: 3995254 (1976-11-01), Rosenbaum
patent: 4010445 (1977-03-01), Hoshino
patent: 4034194 (1977-07-01), Thomas et al.
patent: 4053871 (1977-10-01), Vidalin et al.
patent: 4058795 (1977-11-01), Balm
patent: 4058851 (1977-11-01), Scheuneman
patent: 4136395 (1979-01-01), Kolpek et al.
patent: 4149262 (1979-04-01), Lamb et al.
patent: 4157586 (1979-06-01), Gannon et al.
patent: 4157587 (1979-06-01), Joyce et al.
patent: 4164025 (1979-08-01), Dubnowski et al.
patent: 4187551 (1980-02-01), Nutter et al.
Riseman and Hanson, A Contextual Postprocessing System for Error Correction Using Binary n-Grams, IEEE Trans. on Computers, vol. C-23, No. 5, May 1974, pp. 480-493.
Ascher, et al., An Interactive System for Reading Unformatted Printed Text, _IEEE Transaction on Computers, vol. C-20, No. 12, Dec. 1971, pp. 1527-1543.
Bloom, Space/Time Trade-Offs in Hash Coding with Allowable Errors, Communication of the ACM, vol. 13, No. 7, Jul. 1970, pp. 422-426.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for testing membership in a set through has does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for testing membership in a set through has, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for testing membership in a set through has will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-393576

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.