Compressing Pattern Databases

Ariel Felner, Ram Meshulam, Robert C. Holte, Richard E. KorfAAAI 2004

Abstract

Heuristic search algorithms like A and IDA rely on informed heuristic functions to find optimal solutions efficiently. Pattern Databases (PDBs) provide high-quality heuristics by precomputing subproblem costs, but their utility is often restricted by available memory. This paper introduces compression techniques—both lossy and lossless—that merge adjacent, highly correlated PDB entries. By prioritizing the inclusion of larger, more descriptive subproblems over individual entry precision, these methods achieve search speedups of up to three orders of magnitude on classic benchmarks like the Towers of Hanoi and sliding tile puzzles.

Introduction

The performance of heuristic search is fundamentally tied to the accuracy of the heuristic function $h(n)$. Pattern Databases have emerged as a dominant method for generating heuristics by storing exact costs for subproblems in large lookup tables. However, as problem complexity grows, the size of an effective PDB often exceeds the available RAM, leading to a "memory wall." When a PDB spills onto disk, search performance degrades significantly due to slow I/O operations.

Historically, researchers maintained a strict 1:1 mapping between subproblem states and PDB entries. This work challenges that paradigm, exploring how to compress massive PDBs into limited memory budgets while preserving their search-guiding power.

Compression Methodology

The core insight of this work is that adjacent states in a search space—those reachable via a single move—typically possess very similar heuristic values. The authors exploit this local correlation through two primary strategies:

  1. Lossy Compression: Multiple adjacent PDB entries are merged into a single entry. To ensure the heuristic remains admissible (never overestimating the true cost), the merged entry stores the minimum value of its constituent states. While this introduces minor information loss, it allows the search to utilize much larger abstractions that would otherwise be impossible to fit in memory.
  2. Lossless Compression: This approach stores the minimum value of a group of entries along with a few additional bits per entry to reconstruct the original exact values. This offers memory savings with zero accuracy loss, though it incurs a slight computational overhead during search for decoding.

A critical component of effective compression is the indexing function. By mapping "cliques"—groups of states that are mutual neighbors—to adjacent indices in the database, the authors maximize the correlation within merged blocks, thereby minimizing the error introduced by lossy compression.

Illustration of indexing cliques to group correlated states for compression.

Experimental Evaluation

The proposed methods were evaluated on two standard search benchmarks: the 4-peg Towers of Hanoi (TOH4) and the Sliding Tile Puzzle (15-puzzle and 24-puzzle).

Towers of Hanoi

In the TOH4 domain, the researchers tested configurations with 16 to 18 disks. The results demonstrated that a "lossy" version of a large PDB (e.g., 16 disks) is often far more effective than a "perfect" version of a smaller PDB (e.g., 14 disks). By using a compressed 16-disk PDB, the 18-disk problem was solved in just 463 seconds—a significant improvement over previous state-of-the-art methods that required hours or massive memory resources.

Search performance on large Towers of Hanoi problems using compressed PDBs.

Sliding Tile Puzzles

For the 15-puzzle, the authors achieved an average solution time of 16 milliseconds by taking the maximum of four different compressed PDBs. This performance surpassed previous benchmarks while utilizing less memory. The efficiency was further enhanced by "heuristic offsetting," where the PDB stores the difference between the true cost and the Manhattan Distance, a value that is even more highly correlated among neighbors.

Conclusion

Compressing Pattern Databases by exploiting local state-space structure allows for the use of significantly larger and more informed heuristics within fixed memory constraints. This approach effectively trades a small amount of local precision for a global increase in heuristic quality, leading to dramatic reductions in search time. Future work may involve exploring more complex data structures like tries or leveraging machine learning models to approximate PDB values, potentially scaling these techniques to even larger problem domains.

Summary updated

BibTeX
@inproceedings{felner2004compressing,
  author = {Ariel Felner and Ram Meshulam and Robert C. Holte and Richard E. Korf},
  title = {{Compressing Pattern Databases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2004},
}
Figure