Constructing Minimal Perfect Hash Functions Using SAT Technology

Sean A. Weaver, Marijn HeuleAAAI 2020 · DOI

Introduction

A Minimal Perfect Hash Function (MPHF) provides a collision-free mapping from a set of $n$ keys to the first $n$ integers. This data structure is essential for high-performance indexing, allowing for unique "addresses" in a database without wasting any space. The theoretical "Holy Grail" of MPHF research is the information-theoretic limit: the absolute minimum space required to store such a function is approximately 1.44 bits per key.

While theoretical constructions for this limit exist, practical algorithms typically require 2 to 4 bits per key. For massive databases with billions of entries, this gap represents gigabytes of overhead. Researchers from the NSA and Carnegie Mellon University have recently applied Boolean satisfiability (SAT) technology to bridge this gap, introducing methods that reach the theoretical limit for small sets and provide highly efficient practical alternatives for large-scale data.

SAT-Based Optimal Construction

The researchers first treated the search for an MPHF as a SAT problem. By representing the hash index of each key as a bit-vector, they used a SAT solver to find variable assignments that guarantee no two keys map to the same index.

Two primary encodings were tested:

  • Compact Encoding ($O(n^2 \log n)$ clauses): Uses auxiliary variables to represent equality.
  • Cubic Encoding ($O(n^3)$ clauses): Explicitly forbids collisions between every pair of keys for every possible index.

Counter-intuitively, the larger $O(n^3)$ encoding performed significantly better. The additional clauses allowed the SAT solver to perform more unit propagations, enabling it to identify contradictions earlier and prune the search space more effectively. This "bigger is better" paradox highlights how formula structure can be more important than formula size in SAT solving.

Phase Transitions and the 1.44-Bit Limit

A key contribution of this work is the empirical verification of the information-theoretic limit using SAT solvers. The researchers observed a sharp "phase transition" in solvability. When the allowed space is below 1.44 bits per key, the problem is almost always unsatisfiable (UNSAT). Just above this threshold, it becomes solvable (SAT).

Figure 2: The percentage of satisfiable instances drops sharply as the space per key approaches the theoretical limit of 1.44 bits (left), while the runtime of the SAT solver peaks at this same transition point (right).

As shown in the figure above, the difficulty of the problem (measured by runtime) spikes exactly at the boundary where the probability of satisfiability shifts. This confirms that SAT solvers can find solutions right at the mathematical edge of possibility.

Practical Scaling: The 1.83n Construction

Because pure SAT solvers struggle with sets larger than $n \approx 40$, the authors developed a second, more practical construction for massive datasets. This approach uses weighted bipartite graphs and the Hungarian algorithm to find a minimum-weight perfect matching. This matching is then stored in an XORSAT filter, a space-efficient retrieval structure.

To handle datasets exceeding a billion keys, the construction is "sharded" into smaller, manageable blocks. This makes the process trivially parallelizable and maintains high efficiency.

Key Results and Performance

The SAT-based approach successfully constructed MPHFs for small sets at or below the 1.44 bits/key limit, outperforming previous brute-force methods. For larger sets, the empirical bits-per-key requirement ($\alpha_n$) converges toward the theoretical limit as $n$ increases.

Figure 5: Empirical bits-per-key requirements (alpha_n) for various set sizes (n), showing convergence toward the 1.44 limit.

In practical testing on $2^{30}$ (over 1 billion) keys, the 1.83n construction achieved:

  • Space Efficiency: A consistent 1.85 bits per key (including overhead).
  • Query Speed: Approximately 550 nanoseconds per query, or 1.8 million queries per second.

Conclusion and Future Work

By leveraging SAT technology, this research has pushed MPHF construction closer to theoretical limits than previously possible in practice. While the pure SAT approach is currently limited to small sets, the 1.83n construction offers a state-of-the-art balance of space and speed for billion-scale datasets. Future work may involve specialized local-search SAT solvers to scale the optimal 1.44-bit construction to even larger sets.

Summary updated

BibTeX
@inproceedings{weaver2020constructing,
  author = {Sean A. Weaver and Marijn Heule},
  title = {{Constructing Minimal Perfect Hash Functions Using SAT Technology}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5529},
}
Figure