A Comparison of Time-Space Schemes for Graphical Models

Mateescu, Robert; Dechter, Rina

A Comparison of Time-Space Schemes for Graphical Models

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2346-2351.

Abstract

We investigate three parameterized algorithmic schemes for graphical models that can accommodate trade-offs between time and space: 1) AND/OR Adaptive Caching (AOC(i)); 2) Variable Elimination and Conditioning (VEC(i)); and 3) Tree Decomposition with Conditioning (TDC(i)). We show that AOC(i) is better than the vanilla versions of both VEC(i) and TDC(i), and use the guiding principles of AOC(i)to improve the other two schemes. Finally, we show that the improved versions of VEC(i) and TDCI can be simulated by AOC(i), which emphasizes the unifying power of the AND/OR framework.

Robert Mateescu, and Rina Dechter. 2007. A Comparison of Time-Space Schemes for Graphical Models. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 2346–2351. https://ijcai.org/proceedings/2007/378

@inproceedings{ijcai2007p378,
  title     = {A Comparison of Time-Space Schemes for Graphical Models},
  author    = {Mateescu, Robert and Dechter, Rina},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {2346--2351},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/378},
}

TY  - CPAPER
TI  - A Comparison of Time-Space Schemes for Graphical Models
AU  - Mateescu, Robert
AU  - Dechter, Rina
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 2346
EP  - 2351
UR  - https://ijcai.org/proceedings/2007/378
ER  -