LOGARITHMIC-TIME UPDATES AND QUERIES IN PROBABILISTIC NETWORKS

Traditional databases commonly support efficient query and update proc edures that operate in time which is sublinear in the size of the data base. Our goal in this paper is to take a first step toward dynamic re asoning in probabilistic databases with comparable efficiency. We prop ose a dynamic data structure that supports efficient algorithms for up dating and querying singly connected Bayesian networks. In the convent ional 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 propos e 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 it self in applications requiring (near) real-time response over large pr obabilistic databases. We briefly discuss a potential application of d ynamic probabilistic reasoning in computational biology.