Approximated ZDD Construction Considering Inclusion Relations of Models

Zero-suppressed binary decision diagrams (ZDDs) are data structures that can represent families of sets in compressed form. By using ZDDs, we can perform several useful operations over families of sets in time polynomial to ZDD size. However, a ZDD representing a large family of sets tends to consume a prohibitive amount of memory. In this paper, we attempt to reduce ZDD size by allowing them to have some false positive entries. Such inexact ZDDs are still useful for optimization and counting problems since they permit only false positive errors. We propose two algorithms that can reduce ZDD size without making any false negative errors. The first is a general algorithm that can be applied to any ZDD. The second one is a faster algorithm that can be used if the ZDD represents a monotone family of sets. Our algorithms find pairs of nodes in a ZDD that do not yield any false negatives if they are merged, and then merge those pairs in a greedy manner to reduce ZDD size. Furthermore, our algorithms can be easily combined with existing top-down ZDD construction methods to directly construct approximated ZDDs. We conduct experiments with representative benchmark datasets and empirically confirm that our proposed algorithms can construct ZDDs with 1,000 times fewer false positives than those made with baseline methods, when the ZDD sizes are halved from the original sizes.

1. 1.

   Heavy branch subsetting was originally proposed for BDDs. We slightly modify it to suit ZDDs. In this method, when we want to delete node u with label k, we incorporate u into node \(p_k\) such that \(\mathcal {F}_{p_k} = 2^{\{k,k+1,\cdots ,c\}}\). There can be several node selection methods such as [15, 18]. In our experiment, we decide nodes to delete similarly to our proposed method.

2. 2.

   http://www.topology-zoo.org/dataset.html.

3. 3.

   http://fimi.uantwerpen.be/data/.

Authors and Affiliations

1. Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan

   Kotaro Matsuda & Shuhei Denzumi

2. NTT Communication Science Laboratories, NTT Corporation, Kyoto, Japan

   Kengo Nakamura, Masaaki Nishino & Norihito Yasuda

Corresponding author

Correspondence to Kotaro Matsuda .

Editors and Affiliations

1. Wilfrid Laurier University, Waterloo, ON, Canada

   Ilias Kotsireas

2. University of Florida, Gainesville, FL, USA

   Panos Pardalos

3. University of Ioannina, Ioannina, Greece

   Konstantinos E. Parsopoulos

4. Delft University of Technology, Delft, The Netherlands

   Dimitris Souravlias

5. University of Florida, Gainesville, FL, USA

   Arsenis Tsokas

A Speeding Up Finding Inclusion Relations Under Monotonicity

In this section, we explain how to reduce the time complexity of Algorithm 1 to O\((|G|\alpha (|G|))\). Assume that we visit node q in a while loop of Algorithm 1 and reach node \(q'\) at the end of the loop. After that, we know that a desired node exists at least after \(p'\) when we traverse the same route in the same while loop because of the loop conditions. Thus, traversing nodes one by one every time is redundant and can be avoided. For example, when we finished processing of nodes in layer \(L_k\), we know that we can ignore the nodes with label smaller than k while computing \(sup(\cdot )\) of nodes in lower layers. Therefore, we want to avoid traversing \(sup(\cdot )\) one by one and instead skip them to reach nodes in desired layers. Using disjoint-set data structures to store nodes already processed allows us to execute while loops in Algorithm 1 efficiently. The disjoint-set data structure stores multiple sets that are mutually disjoint. Each set stored in disjoint-set data structure has one representative element in the set. Disjoint-set data structure supports two operations: (1) union operation merges two sets into one and updates its representative; (2) find operation returns the representative of a set. Indeed, we have to prepare four disjoint-set data structures as follows: (1) Skip continuous \(sup(\cdot )\) if \(p \in P_0\) is in the first while loop (2) Skip continuous \(sup(\cdot )\) if \(p \in P_1\) is in the first while loop (3) Skip continuous \(sup(\cdot )\) if \(p \in P_0\) is in the second while loop (4) Skip continuous 0-edges. As a result, the whole computation time of Algorithm 1 is O\((|G|\alpha (|G|))\) and its space complexity is O(|G|).

We store node sets in the ZDD by using four disjoint-set data structures \(DS_1, DS_2, DS_3, DS_4\). Each element in \(DS_i\) corresponds to a node in the ZDD. Let \(ds_i(u)\) be the set that contains u in \({ DS_i}\) and \(rep(ds_i(u))\) be the representative of \(ds_i(u)\). For each node u in the ZDD, \(ds_i(u) = \{u\}\) and \(rep(ds_i(u)) = u\) as an initial value. First, we speed up the repeated updates \(q \leftarrow sup(q)\) in two while loops by using three disjoint-set data structures \(DS_1, DS_2, DS_3\). These are used in the following situations:

1. 1.

   If \(p\in P_0\) is in the first while loop, we use \(DS_1\).

2. 2.

   If \(p\in P_1\) is in the first while loop, we use \(DS_2\).

3. 3.

   If \(p\in P_0\) is in the second while loop, we use \(DS_3\).

We explain only the case of \(p \in P_0\) in the first loop (The other cases are dealt with in the same manner). For each node \(p \in P_0\), let \(p' = rep(ds_1(p))\) and \(q' = rep(ds_1(sup(p')))\). While \(u = zp(q',\ell (u))\), we compute the union of \(ds(p')\) and \(ds(q')\) and set \(rep(ds(p')) = q'\). Then, node \(zp(q',\ell (u))\) is the candidate of sup(u). Since the union and find operations are executed at most O(|G|) times, these operations run in O\((|G|\alpha (|G|))\) time. Second, we explain how to rapidly calculate \(zp(q, \ell (u))\) and \(zp(q_1, \ell (u))\). When we see only 0-edges, a ZDD can be considered as a tree whose root is the terminal node \(\top \) as shown in Fig. 3. When we consider only the nodes included in \(L_1, \ldots , L_k\) \((1\le k \le c+1)\), the induced subgraph of the tree is a forest. Note that each node \(v \in L_1, \ldots , L_k\) belongs to a tree of the forest. If T is a tree of the forest, calculating zp(q, k) is equivalent to finding the node in \(L_k\) and an ancestor of q. We use the disjoint-set data structure \({ DS_4}\) to represent the forest and update it dynamically alongside the processing of layers. When we compute \(sup(\cdot )\) of nodes in \(L_k\), for each 0-edge \((p, p_0)\) such that \(p_0 \in L_k\), we compute the union of \(ds_4(p)\) and \(ds_4(p_0)\) and set the representative of this new set to \(p_0\). This process ensures that \(zp(v, k) = rep(ds_4(u))\) holds. Therefore, we can compute zp(q, k) by finding \(rep(ds_4(q))\) in O\((\alpha (|G|))\) time. The union and find operations are executed O(|G|) times because the number of the 0-edges is |G|. Moreover, \(zp(\cdot , \cdot )\) is called O(|G|) times. Finally, the whole computation time of this algorithm is O\((|G|\alpha (|G|))\).

Reprints and permissions

© 2019 Springer Nature Switzerland AG

Policies and ethics