Bounding Search Space Size via (Hyper)tree Decompositions
This work addresses performance estimation for search algorithms in graphical models, offering significant improvements but is incremental as it builds on existing decomposition methods.
The paper tackled the problem of bounding the performance of AND/OR search algorithms for queries over graphical models by connecting to hypertree decompositions to exploit determinism, resulting in bounds improved by several orders of magnitude on practical instances.
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.