Al. Delcher et al., LOGARITHMIC-TIME UPDATES AND QUERIES IN PROBABILISTIC NETWORKS, The journal of artificial intelligence research, 4, 1996, pp. 37-59
Citations number
24
Categorie Soggetti
Controlo Theory & Cybernetics","Computer Science Artificial Intelligence
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.