Patent ID: 8819037
Filing Date: 2014-08-26
Classification: G06F,G16H

Abstract:
1. A computer implemented method for verifying membership in one or more sets that are subsets of a global set, the method comprising: representing members of the global set by mapping each member to a distinct Boolean variable of length d, wherein 2 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 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 y 1 z 1 , y 1 z 2 , . . . , y k z k , wherein y i and z i represent a first word and a second word of length d-bits or greater and are used to represent the i th clause in the Boolean expression; the j th bit in y i is 1 when the j th 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 j when the Boolean expression is in CNF: the j wherein said representing members of the global set by mapping, said representing a subset of the global set by a Boolean expression, and said determining membership configured by a computing unit programmed to carry out perform the steps of the method using a processor; and wherein a member of the global set, g, represented by a mapping x DNF: g is a member of C if for any i between 1 and k: CNF: g is not a member of C if for any i between 1 and k: