Logarithmic-Time Updates and Queries in Probabilistic Networks
  Traditional databases commonly support efficient 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 first step toward dynamic reasoning in probabilistic
databases with comparable efficiency. We propose a dynamic data structure that
supports efficient algorithms for updating and querying singly connected
Bayesian networks. In the conventional algorithm, new evidence is absorbed in
O(1) time 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 briefly discuss a potential application of dynamic probabilistic
reasoning in computational biology.
