Satisfiability filter and query tool and method of building a satisfiability filter and query tool

A method of building a satisfiability filter comprising the steps of:

• identifying a subset of a domain;
• identifying the elements in the subset;
• selecting a set of hash functions;
• mapping each element of the subset to a set of literals, utilizing the selected set of hash functions;
• combining each set of literals using a Boolean function to create a set of equations;
• conjoining the equations of the set of equations to provide a satisfiability instance;
• creating an array based on a solution to the satisfiability instances;
• identifying an element of a domain to be tested for set membership;
• selecting an element for which set membership is to be tested;
• utilizing the selected set of hash functions to map the selected element to a set of literals;
• combining the literals to create a test equation;
• identifying a solution associated with the satisfiability filter;
• determining whether said test equation is satisfied by the solution associated with the satisfiability filter;
• and
• providing an indication of set membership based upon the determination of whether the test equation is satisfied.

A satisfiability filter query tool implemented by a computer for querying a satisfiability filter to determine membership of an element in a set, the computer including memory for storing information and the tool comprising:

• a hash function identifier for identifying the hash functions used to build the satisfiability filter wherein variables produced by said hash functions range from −n to n;
• a mapper in communication with said hash function identifier for mapping the element to a set of literals utilizing the identified hash functions;
• an equation creator in communication with said mapper wherein said equation creator creates an equation based upon said literals;
• a solution identifier, for receiving the satisfiability filter and identifying a solution to the satisfiability filter stored in memory as an array, said array having a length of n bits;
• a membership checker in communication with said solution identifier and said equation creator;
• wherein said membership checker applies said solution to said equation created by said equation creator and determines whether said solution satisfies said equation;
• and
• an indicator for providing an indication to user indicating whether said element is a member of the set based upon said determination of said membership checker.