Patent ID: 8606771

Claim:
A method for efficient indexing of error tolerant set containment, comprising: obtaining a frequency threshold and a query set; determining all tokens or token sets within the query set; finding all minimal infrequent tokens or all minimal infrequent tokensets of data records and using said minimal infrequent tokens or minimal infrequent tokens sets to build an index; processing the minimal infrequent tokens or minimal infrequent tokensets in a fixed order; determining a collection of signatures for each minimal infrequent token or token set, the collection of signatures covering all variants of the query set; finding a complement of signatures that do not cover variants of the query set; adding the complement of signatures to the collection of signatures if the complement of signatures intersects a current collection of signatures; finding a signature of an uncovered variant of the query set; and adding the signature of the uncovered variant of the query set to the collection of signatures, wherein the collection of signatures covers all variants of the query set.