Search optimization in a computing environment

A system for verifying membership in one or more sets that are subsets of a global set, the system comprising:

• a processor;
• a first logic unit which uses said processor for representing members of the global set by mapping each member to a distinct Boolean variable of length d, wherein 2d is not less than the number of members in the global set;
• a second logic unit which uses said processor for representing a subset of the global set by a Boolean expression which evaluates to a first value for any of the assignments to the Boolean variables which represent members of the subset, and which evaluates to a second value for any of the assignments to the Boolean variables which represent members of the global set that are not members of the subset, wherein the Boolean expression is constructed from one or more subsets so as to be evaluated efficiently for any assignment to the Boolean variables which represent members of the global set;
• and
• a third logic unit which uses said processor for determining membership of a target member of the global set in a target subset of the global set by evaluating the Boolean expression that represents the target subset based on the mapping of the target member wherein the Boolean expressions representing the subsets C of the global set are in disjunctive normal form (DNF) or conjunctive normal form (CNF);
• wherein the Boolean expression is represented by pairs of words y1z1, y1z2, . . . , y-kzk, wherein yi and zi represent a first word and a second word of length d-bits or greater and are used to represent the clause in the Boolean expression;
• the jth bit in yi is 1 when the jth Boolean variable is present in the clause and 0 when it is not present;
• when it is present, then:
• when the Boolean expression is in DNF:
• the jth bit in zi is 1 if the ith Boolean variable is true and 0 otherwise;
• and
• when the Boolean expression is in CNF:
• the jth bit in zi is 0 if the ith Boolean variable is true and 1 otherwise;
• and
• wherein a member of the global set, g, represented by a mapping xg, is tested for membership in C, where:
• DNF:
• g is a member of C if for any i between 1 and k:
• ((xg XOR zi) AND yi)=0;
• CNF:
• g is not a member of C if for any i between 1 and k:
• ((xg XOR zi) AND yi)=0.

A computer program product comprising a non transitory computer readable storage medium having a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

• represent members of a global set by mapping each member to a distinct Boolean variable of length d, wherein 2d is not less than the number of members in the global set;
• represent a subset of the global set by a Boolean expression which evaluates to a first value for any of the assignments to the Boolean variables which represent members of the subset, and which evaluates to a second value for any of the assignments to the Boolean variables which represent members of the global set that are not members of the subset, wherein the Boolean expression is constructed from one or more subsets so as to be evaluated efficiently for any assignment to the Boolean variables which represent members of the global set;
• and
• determine membership of a target member of the global set in a target subset of the global set by evaluating the Boolean expression that represents the target subset based on the mapping of the target member;
• wherein the Boolean expressions representing the subsets C of the global set are in disjunctive normal form (DNF) or conjunctive normal form (CNF);
• wherein the Boolean expression is represented by pairs of words y1z1, y1z2, . . . , y-kzk, wherein yi and zi respectively represent a first word and a second word of length d-bits or greater and are used to represent the clause in the Boolean expression;
• the jth bit in yi is 1 when the jth Boolean variable is present in the clause and 0 when it is not present;
• when it is present, then:
• when the Boolean expression is in DNF:
• the jth bit in zi is 1 if the ith Boolean variable is true and 0 otherwise;
• and
• when the Boolean expression is in CNF:
• the jth bit in zi is 0 if the ith Boolean variable is true and 1 otherwise;
• and
• wherein a member of the global set, g, represented by a mapping xg, is tested for membership in C, where:
• DNF:
• g is a member of C if for any i between 1 and k:
• ((xg XOR zi) AND yi)=0;
• CNF:
• g is not a member of C if for any i between 1 and k:
• ((xg XOR zi) AND yi)=0.