Bounding search space size via (Hyper)tree decompositions

Lars Otten; Rina Dechter

Bounding search space size via (Hyper)tree decompositions

Lars Otten, Rina Dechter

Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:452-459, 2008.

Abstract

This paper develops a measure for bounding the performance of AND/OR search algorithms for solving a variety of queries over graphical models. We show how drawing a connection to the recent notion of hypertree decompositions allows to exploit determinism in the problem specification and produce tighter bounds. We demonstrate on a variety of practical problem instances that we are often able to improve upon existing bounds by several orders of magnitude.

Cite this Paper

BibTeX

@InProceedings{pmlr-vR6-otten08a,
  title = 	 {Bounding search space size via (Hyper)tree decompositions},
  author =       {Otten, Lars and Dechter, Rina},
  booktitle = 	 {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence},
  pages = 	 {452--459},
  year = 	 {2008},
  editor = 	 {McAllester, David A. and Myllymäki, Petri},
  volume = 	 {R6},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {09--12 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://raw.githubusercontent.com/mlresearch/r6/main/assets/otten08a/otten08a.pdf},
  url = 	 {https://proceedings.mlr.press/r6/otten08a.html},
  abstract = 	 {This paper develops a measure for bounding the performance of AND/OR search algorithms for solving a variety of queries over graphical models. We show how drawing a connection to the recent notion of hypertree decompositions allows to exploit determinism in the problem specification and produce tighter bounds. We demonstrate on a variety of practical problem instances that we are often able to improve upon existing bounds by several orders of magnitude.},
  note =         {Reissued by PMLR on 09 October 2024.}
}

Endnote

%0 Conference Paper
%T Bounding search space size via (Hyper)tree decompositions
%A Lars Otten
%A Rina Dechter
%B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence
%C Proceedings of Machine Learning Research
%D 2008
%E David A. McAllester
%E Petri Myllymäki	
%F pmlr-vR6-otten08a
%I PMLR
%P 452--459
%U https://proceedings.mlr.press/r6/otten08a.html
%V R6
%X This paper develops a measure for bounding the performance of AND/OR search algorithms for solving a variety of queries over graphical models. We show how drawing a connection to the recent notion of hypertree decompositions allows to exploit determinism in the problem specification and produce tighter bounds. We demonstrate on a variety of practical problem instances that we are often able to improve upon existing bounds by several orders of magnitude.
%Z Reissued by PMLR on 09 October 2024.

APA

Otten, L. & Dechter, R.. (2008). Bounding search space size via (Hyper)tree decompositions. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:452-459 Available from https://proceedings.mlr.press/r6/otten08a.html. Reissued by PMLR on 09 October 2024.

Related Material

Download PDF