- s the number of splits and, in parentheses, the number of different variables on which the splits occur (different leaves can be split on the same variable).

- p the probability of splitting on a variable it is possible to split on.

- CBN size: the total size (summing over the size of the tables) of the contextual belief network representation.

- BN size: the total size of the factors for the corresponding belief network (i.e., assuming the probabilities are stored in tables).

- CVE time is the runtime (in msecs) of contextual variable elimination and CVE MTS is the maximum sum of the table sizes created for the elimination of a single variable.

- VE time: the runtime (in msecs) of variable elimination and VE MTS is the maximum table size created for the elimination of a single variable.

## References

Becker, A. and Geiger, D. (1996). A sufficiently fast algorithm for finding close to optimal junction trees, in E. Horvitz and F. Jensen (eds), *Proc. Twelfth Conf. on Uncertainty in Artificial* Intelligence (UAI-96), Portland, OR, pp. 81–89.

Bertelè, U. and Brioschi, F. (1972). *Nonserial dynamic programming*, Vol. 91 of *Mathematics in* Science and Engineering, Academic Press.

Boutilier, C. (1997). Correlated action effects in decision theoretic regression, in Dan Geger and Prakash Shenoy (ed.), *Proceedings of the Thirteenth Annual Conference on Uncertainty in* Artificial Intelligence (UAI–97), Providence, Rhode Island, pp. 30–37.

Boutilier, C., Dearden, R. and Goldszmidt, M. (1995). Exploiting structure in policy construction, Proc. 14th International Joint Conf. on Artificial Intelligence (IJCAI-95), Montréal, Québec, pp. 1104–1111.

Boutilier, C., Friedman, N., Goldszmidt, M. and Koller, D. (1996). Context-specific independence in Bayesian networks, in E. Horvitz and F. Jensen (eds), *Proc. Twelfth Conf. on Uncertainty in* Artificial Intelligence (UAI-96), Portland, OR, pp. 115–123.

Chickering, D. M., Heckerman, D. and Meek, C. (1997). A Bayesian approach to learning Bayesian networks with local structure, *Proc. Thirteenth Conf. on Uncertainty in Artificial Intelligence* (UAI-97), pp. 80–89.

Dagum, P. and Luby, M. (1993). Approximating probabilistic inference in Bayesian belief networks is NP-hard, *Artificial Intelligence* 60(1): 141–153.

D'Ambrosio (1995). Local expression languages for probabilistic dependence, *International Journal* of Approximate Reasoning 13(1): 61–81.