Lossy Compression of Pattern Databases Using Acyclic Random Hypergraphs

Mehdi Sadeqi, Howard J. HamiltonIJCAI 2017 · DOI

TL;DR

This paper introduces Acyclic Random Hypergraph Compression (ARHC), a novel method for compressing Pattern Databases (PDBs) used in AI search. ARHC offers a better trade-off between compression rate and heuristic accuracy compared to existing Bloom filter-based approaches, leading to significantly faster search performance.

What Problem Does This Paper Address?

In Artificial Intelligence, search algorithms like A and IDA rely on heuristic functions to guide their search for optimal solutions. Pattern Databases (PDBs) are a common way to generate accurate, admissible heuristic functions. However, PDBs can become extremely large, exceeding available memory. This necessitates compression techniques. While lossless compression methods exist, they often don't reduce memory usage enough. Lossy compression methods aim to reduce memory further by sacrificing some heuristic accuracy, but must guarantee that the heuristic remains admissible (never overestimates the cost to the goal). Existing lossy methods like min-compression and Partial Pattern Databases (PPDBs) have limitations. PPDBs, especially when implemented with Bloom filters, show promise but can still be outperformed. This paper addresses the need for a lossy PDB compression technique that achieves high compression rates while minimizing heuristic information loss and improving search efficiency.

Methods

The paper proposes Acyclic Random Hypergraph Compression (ARHC), a domain-independent approach that leverages acyclic random r-partite r-uniform hypergraphs. The core idea is to represent a PDB using a lookup table derived from such a hypergraph.

The ARHC process involves two main steps:

  1. Mapping: An acyclic random r-partite r-uniform hypergraph is generated. This involves repeatedly creating random hypergraphs until an acyclic one is found. The paper notes that for a graph with $V$ vertices and $E$ edges, acyclic ones are more probable when $V \ge c(r)|E|$, with $r=3$ being a good candidate. A specific algorithm is used to detect cycles.
  2. Assigning: Values are assigned to the vertices of the hypergraph, which correspond to entries in the lookup table. This is done by traversing the hyperedges and assigning values such that the sum of values for vertices in an edge, modulo a certain value, equals the heuristic value of the corresponding abstract state.

ARHC is presented in two versions:

  • ARHC-Base: This version aims for higher compression. It uses a lookup table where entries are calculated using three hash functions and a modulo operation. Values greater than a threshold $v$ are treated as $v+1$.
  • ARHC-Extended: This version improves heuristic quality by using more bits per entry in the lookup table, thus increasing the probability of retrieving the correct value for states with heuristic values greater than $v$.

The paper also contrasts ARHC with the Level-by-Level Bloom Filter approach, where each depth of an abstraction is represented by a Bloom filter.

Datasets

The paper evaluates ARHC on three problem domains:

  • Sliding-Tile Puzzle: Specifically, a 3x4 version with two different projection abstractions.
  • Blocks World with Table Positions: A domain with 12 blocks and 3 table positions, using two domain abstractions.
  • Scanalyzer: A 10-Belt Scanalyzer domain with two domain abstractions.

The abstractions used are described in detail in Table 1, noting the number of abstract states and maximum heuristic values for each. The experiments use uniformly generated random problem instances for evaluation.

Key Insights and Ideas

  • Hypergraphs as a Compression Tool: The core innovation is using acyclic random hypergraphs to structure the PDB lookup table, enabling efficient compression.
  • Trade-off Management: ARHC explicitly manages the trade-off between compression rate and heuristic accuracy through its Base and Extended versions, allowing users to choose based on their needs.
  • Domain Independence: The ARHC approach is designed to be domain-independent, making it broadly applicable across various AI planning problems.
  • Superiority over Bloom Filters: The experimental results strongly suggest that ARHC, particularly the Extended version, offers a significant advantage over Bloom filter-based PPDBs in terms of heuristic accuracy, search efficiency, and space usage.
  • Amortized Construction Cost: While ARHC construction can be more time-consuming than Bloom filters, this overhead is amortized over potentially many problem-solving instances, making it cost-effective in practice.

Key Results

  • Improved Search Performance: ARHC consistently outperformed Bloom PPDBs across all tested abstractions and sizes.
  • Bloom PPDBs expanded 1.4 to 11.3 times more nodes than ARHC.
  • Bloom PPDBs required 1.6 to 14.5 times more time for problem solving.
  • Higher Heuristic Accuracy: ARHC consistently provided a higher average heuristic value compared to Bloom PPDBs.
  • Space Efficiency: ARHC PPDBs generally occupied less space than comparable Bloom PPDBs.
  • Construction Time: ARHC construction was between 1.4 and 2.3 times longer than Bloom PPDB construction, but this was deemed acceptable due to amortization.

Limitations and Future Work

  • Construction Time: The paper acknowledges that ARHC's construction time is higher than Bloom filters, though it argues this is offset by amortized benefits.
  • Information Loss: While ARHC minimizes information loss, it is still a lossy compression method, and some heuristic information is lost for states with heuristic values greater than $v$.
  • Future Work:
    • Merging Depths: The authors suggest exploring methods to merge consecutive depths in the range $[0, v]$ to further reduce information loss, potentially by defining a "merge function" to determine which depths to combine.
  • Combining with Other Techniques: Investigating ARHC's compatibility and potential improvements when combined with other compression strategies like 1.6-bit pattern databases.

Summary updated

BibTeX
@inproceedings{sadeqi2017lossy,
  author = {Mehdi Sadeqi and Howard J. Hamilton},
  title = {{Lossy Compression of Pattern Databases Using Acyclic Random Hypergraphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/611},
}
Figure