BEEM : Bucket Elimination with External Memory

Kalev Kask, Rina Dechter, Andrew GelfandUAI 2010

TL;DR

This paper introduces BEEM, an extension of the Bucket Elimination algorithm that leverages disk memory to tackle probabilistic inference problems too large for main memory. By carefully managing disk I/O and parallelizing computations, BEEM successfully solves problems previously intractable for exact inference methods, demonstrating significant scalability improvements.

What Problem Does This Paper Address?

Exact inference algorithms for probabilistic graphical models, like Bucket Elimination (BE), are powerful but suffer from a critical limitation: their memory requirements grow exponentially with the "induced width" of the problem. This means that even moderately complex real-world problems can quickly exceed the capacity of available RAM, rendering these exact methods unusable. While some algorithms trade computation time for reduced memory usage, this paper aims to push the boundaries further by incorporating external (disk) memory into the inference process, effectively offering a much larger memory pool at the cost of slower access.

Methods

The core contribution is the extension of the Bucket Elimination (BE) algorithm to utilize disk memory, creating BEEM (Bucket Elimination with External Memory). This involves several key innovations:

  • Disk-Based Function Storage: Intermediate functions, which can become massive, are stored on disk in blocks.
  • Block-Based Processing: Functions are divided into blocks that fit into main memory. The algorithm loads necessary blocks from disk, performs computations, and saves results back to disk.
  • Optimized I/O: A primary focus is minimizing disk reads and writes. This is achieved through:
  • Function Table Indexing: Carefully ordering variables within function scopes to ensure that entries needed for a computation are likely to reside in the same disk block, reducing the number of block loads. This ordering is guided by the bucket tree structure.
  • Block Size Computation: Determining optimal block sizes for functions to balance memory usage across threads and satisfy constraints imposed by the bucket tree structure.
  • Parallelization: The algorithm is designed to run on multiple threads, allowing computations to proceed while other threads handle disk I/O, mitigating the latency of disk access.

Datasets

The paper evaluates BEEM on two types of problems:

  • Pedigree Problems: Derived from genetics, these problems involve a few hundred to a thousand variables.
  • Type 4 Linkage Problems: These are larger problems with several thousand variables, specifically chosen for their high induced width.

These datasets were used in the UAI-2008 solver competition, and the paper notes that many of these problems were not solved by other participants.

Key Insights and Ideas

  • Disk as a Viable Memory Extension: The paper demonstrates that with careful algorithmic design, disk memory can be effectively integrated into exact inference, opening up previously intractable problem spaces.
  • I/O Optimization is Paramount: The significant difference in access speed between RAM and disk means that minimizing disk I/O operations is the most crucial factor for performance. Naive approaches that treat disk like RAM are prohibitively slow.
  • The Bucket Tree is Key: The inherent structure of the bucket tree, derived from variable elimination orderings, provides a powerful framework for guiding both function scope ordering and block size computations, ensuring monotonicity and efficient I/O.
  • Parallelism Masks Latency: By overlapping computation with I/O using multiple threads, the performance penalty of disk access can be significantly reduced.

Key Results

BEEM demonstrates impressive scalability:

  • Solves Previously Intractable Problems: BEEM successfully computed exact solutions for several pedigree problems (specifically problems 7, 9, 13, 31, 34, 41, 50, and 51) for which no exact solution was previously known.
  • Competitive Performance: While BEEM incurs overhead due to multithreading and disk management, it significantly outperforms VEC (Variable Elimination and Conditioning) and ACE (a software package for exact inference) on problems that do not fit into RAM. For problems that fit into RAM, VEC and ACE can be faster due to lower overhead.
  • Scalability on Large Problems: For large type-4 linkage problems, BEEM consistently solves problems that VEC and ACE cannot due to memory limitations, often completing them within hours while others exceed 24 hours or run out of memory.

Limitations and Future Work

  • Block Size Optimization: The paper acknowledges that the block size computation algorithm provides a feasible but potentially suboptimal solution. Further research is suggested to minimize unutilized memory more effectively.
  • Handling "Gaps" in Scopes: The paper notes that "gaps" in variable scopes (where a variable in the output function's scope is not present in an input function's scope) can lead to non-monotonicity and inefficient I/O. This issue is currently untreated, and the authors are exploring various approaches.
  • Generalization: Future work includes extending BEEM for belief updating on variables other than the root and handling more general tree decompositions. The authors also plan to further improve table decomposition and computation schemes.

Summary updated

BibTeX
@inproceedings{kask2010beem,
  author = {Kalev Kask and Rina Dechter and Andrew Gelfand},
  title = {{BEEM : Bucket Elimination with External Memory}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2010},
}
Figure