Scalable Algorithms for Approximate DNF Model Counting
This addresses a key bottleneck in probabilistic inference and database systems, offering a scalable solution for large-scale problems, though it is an incremental improvement over existing Monte Carlo methods.
The paper tackles the computationally intractable problem of approximate DNF model counting, which is critical for applications like probabilistic inference and database queries, by developing a new Monte Carlo approach with adaptive stopping and short-circuit evaluation. The result is an algorithm that is proven to achieve PAC bounds, is asymptotically more efficient than prior methods, and experimentally outperforms them by orders of magnitude, scaling to problems with millions of variables.
Model counting of Disjunctive Normal Form (DNF) formulas is a critical problem in applications such as probabilistic inference and network reliability. For example, it is often used for query evaluation in probabilistic databases. Due to the computational intractability of exact DNF counting, there has been a line of research into a variety of approximation algorithms. These include Monte Carlo approaches such as the classical algorithms of Karp, Luby, and Madras (1989), as well as methods based on hashing (Soos et al. 2023), and heuristic approximations based on Neural Nets (Abboud, Ceylan, and Lukasiewicz 2020). We develop a new Monte Carlo approach with an adaptive stopping rule and short-circuit formula evaluation. We prove it achieves Probably Approximately Correct (PAC) learning bounds and is asymptotically more efficient than the previous methods. We also show experimentally that it out-performs prior algorithms by orders of magnitude, and can scale to much larger problems with millions of variables.