Logarithmic-Time Updates and Queries in Probabilistic Networks
This work addresses the need for efficient, sub-linear processing in probabilistic networks, which is crucial for applications requiring real-time performance, though it is incremental as it builds on existing algorithms for specific network types.
The paper tackles the problem of slow query processing in singly connected Bayesian networks by introducing a dynamic data structure that reduces query time from O(N) to O(log N) after preprocessing, at the cost of O(log N) per evidence update, enabling near real-time responses in large probabilistic databases.
In this paper we propose a dynamic data structure that supports efficient algorithms for updating and querying singly connected Bayesian networks (causal trees and polytrees). In the conventional algorithms, new evidence in absorbed in time O(1) and queries are processed in time O(N), where N is the size of the network. We propose a practical algorithm which, after a preprocessing phase, allows us to answer queries in time O(log N) at the expense of O(logn 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.