Logarithmic-time updates and queries in probabilistic networks

Traditional databases commonly support e cient 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 e ciency. We propose a dynamic data structure that supports e cient 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(log N) at the expense of O(log N) 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