---
title: "Optimal Time-Space Tradeoff in Probabilistic Inference"
authors:
  - "David Allen"
  - "Adnan Darwiche"
doi: ""
url: "https://ijcai.org/proceedings/2003/139"
pdf: "https://ijcai.org/proceedings/2003/0139.pdf"
venue: "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence"
year: 2003
pages: "969-974"
track: ""
keywords:
---

# Optimal Time-Space Tradeoff in Probabilistic Inference

David Allen, Adnan Darwiche

*Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence*, pages 969-974.

## Abstract

Recursive Conditioning, RC, is an any-space algorithm for exact inference in Bayesian networks, which can trade space for time in increments of the size of a floating point number. This smooth tradeoff is possible by varying the algorithm's cache size. When RC is run with a constrained cache size, an important problem arises: Which specific results should be cached in order to minimize the running time of the algorithm? RC is driven by a structure known as a dtree, and many such dtrees exist for a given Bayesian network. In this paper, we examine the problem of searching for an optimal caching scheme for a given dtree, and present some optimal time-space tradeoff curves for given dtrees of several published Bayesian networks. We also compare these curves to the memory requirements of state-of- the-art algorithms based on jointrees. Our results show that the memory requirements of these networks can be significantly reduced with only a minimal cost in time, allowing for exact inference in situations previously impractical. They also show that probabilistic reasoning systems can be efficiently designed to run under varying amounts of memory.