Home > Publications > Reports > Informatics (CW)


CW 586

Theofrastos Mantadelis and Gerda Janssens
Variable compression in ProbLog

Abstract

The paper identifies patterns of Boolean variables that occur in Boolean formulae, namely AND-clusters and OR-clusters. We give a polynomial algorithm that detects AND-clusters in disjunctive normal form (DNF) Boolean formulae, or OR-clusters in conjunctive normal form (CNF) Boolean formulae. Furthermore, we explain how to exploit the clusters in the context of ProbLog.

In ProbLog, Boolean formulae are used to express how the probability of a query depends on the probabilistic part of a ProbLog program. Boolean formulae in ProbLog are represented by Reduced Ordered Binary Decision Diagrams (ROBDD). Depending on the Boolean formula, the generation of a ROBDD can be very costly. In this paper we present how to compress clusters in Boolean formulae and make the generation of the ROBDD more efficient without affecting the probability of the query.

We did an experimental evaluation of the effects of AND-cluster compression for a real application of ProbLog. With our prototype implementation we have a significant improvement in performance (up to 87%) for the generation of ROBDDs.

report.pdf (394K) / mailto: T. Mantadelis