Other

The Government of the United Statesrepresented by the Director, National Security Agency

Sean A Weaver

Katrina Jean Ray

Victor W Marek

Andrew J Mayer

A computer-implemented method of constructing a minimal perfect hash function includes selecting a set H of k hash functions over a set Y of n keys and building a bipartite graph from keys to hash values using the set Y of keys and the set H of hash functions. Each edge of the bipartite graph has a weight equal to an index of a hash function associated with that edge. The method also includes determining a minimal weight perfect matching of the bipartite graph and generating an XORSAT filter using the minimal weight perfect matching of the bipartite graph, such that a minimal perfect hash function can be performed on an element by querying the XORSAT filter for a result associated with the element.

Systems and methods of minimal perfect hashing with XORSAT filters

A SAT filter builder and method for building a SAT filter is provided. Hash functions are utilized to map elements of a domain subset to a set of literals which are in turn used to create a set of equations. These equations are conjoined to provide a satisfiability instance. The satisfiability instance is provided to an equation solver and the solution is provided to an array to build the filter. A query tool is also provided which allows the filter built by the SAT filter to test an element for set membership. The query tool utilizes the same hash functions used by the SAT filter builder to map the element to be tested to a set of literals. These literals are used to create an equation. The solution identified by the SAT builder tool is then provided to the equation created by the query tool and set membership is determined by determining whether the equation provided by the query tool is satisfied by the solution provided by the SAT filter builder.

Growing community of inventors

Baltimore, MD, United States of America

Sean A Weaver