Technical Reports

The ICICS/CS Reading Room

UBC CS TR-2006-08 Summary

Local Consistency in Junction Graphs for Constraint-Based Inference, March 28, 2006 L. Chang and A. K. Mackworth, 11 pages

The concept of local consistency plays a central role in constraint satisfaction and has been extended to handle general constraint-based inference (CBI) problems. We propose a family of novel generalized local consistency concepts for the junction graph representation of CBI problems. These concepts are based on a general condition that depends only on the existence and property of the multiplicative absorbing element and does not depend on the other semiring properties of CBI problems. We present several local consistency enforcing algorithms and their approximation variants. Theoretical complexity analyses and empirical experimental results for the application of these algorithms to both MaxCSP and probability inference are given. We also discuss the relationship between these local consistency concepts and message passing schemes such as junction tree algorithms and loopy message propagation.

If you have any questions or comments regarding this page please send mail to