Logarithmic-time updates and queries in probabilistic networks

Traditional databases commonly support ecient query and update procedures that operate in time which is sublinear in the size of the database. Our goal in this paper is to take a rst step toward dynamic reasoning in probabilistic databases with comparable eciency. We propose a dynamic data structure that supports ecient algorithms for updating and querying singly connected Bayesian networks. In the conventional algorithm, new evidence is absorbed in time O(1) and queries are processed in time O(N), where N is the size of the network. We propose an algorithm which, after a preprocessing phase, allows us to answer queries in time O(logN) at the expense of O(logN) time per evidence absorption. The usefulness of sub-linear processing time manifests itself in applications requiring (near) real-time response over large probabilistic databases. We brie y discuss a potential application of dynamic probabilistic reasoning in computational biology. 1