<p><strong>The minimum size of a BDD node.</strong> A BDD node must contain enough storage for pointers to the low + high nodes, and optionally the variable index. Let's treat these in turn.</p>
<ul>
<li><strong>The <code>low</code> and <code>high</code> pointers.</strong> The two pointers must each have length <span class="math-container">$\log_2(m^\ast)$</span> if a node can point to <span class="math-container">$m^\ast$</span> different other nodes. Here I mean that a node halfway down the diagram cannot point &quot;up&quot;, so in principle this pointer only needs to distinguish between the nodes below it. Unfortunately, there is no good way to take advantage of this by achieving an <span class="math-container">$m^\ast$</span> which is much smaller than the total number of nodes <span class="math-container">$m$</span> in your diagram. To see this, I remark that a completely populated BDD has <span class="math-container">$2^k$</span> nodes at layer <span class="math-container">$k$</span> (counting from the root), and will have <span class="math-container">$m^\ast\geq \frac 12m-o(m)$</span>. So unfortunately you cannot save any bits in these pointers by taking advantage of this fact.</li>
<li><strong>The variable index.</strong> If only <span class="math-container">$n$</span> variables appear in the problems you wish to solve using BDDs, then only <span class="math-container">$\left\lceil \log_2(n+1) \right\rceil$</span> bits are required for the variable index. For example, the <a href="https://github.com/cda-tum/dd_package/blob/40dba96ea44a022c855cd2c2c6600a73b8f19059/include/dd/Definitions.hpp" rel="nofollow noreferrer">MQT library</a> uses a 7-bit index, instead of 32 bits, because its intended use case is problems with up to 128 variables. Indeed, in some BDD versions, each node is connected only to nodes on the next layer, so a variable index is redundant.</li>
</ul>
<p><strong>Minimum node size is not the only objective.</strong> Achieving the minimum possible size per node is a good objective. Nevertheless, it is a design choice which is traded off against several other competing objectives that you have when implementing BDD software. The most important other objective is speed: speed is a bottleneck just as often as memory. For example:</p>
<ul>
<li>for this reason, many implementations have a <code>visited</code> bit on each node, which speeds up operations such as counting the number of nodes in a node's subtree, and counting the number of satisfying assignments (the MQT implementation has this, but Microsoft's does not).</li>
<li>Many implementations have a <code>flippped</code> bit on each node (or each edge), indicating whether the node represents the function <span class="math-container">$f$</span> or <span class="math-container">$\neg f$</span> (Microsoft's implementation has this).</li>
</ul>
<p>More broadly, it is admissible to use a different architecture with larger nodes, if that results in a more succinct diagram. For example,</p>
<ul>
<li>SDDs have nodes that are unbounded in size, but can be exponentially smaller than BDDs in some cases, even when taking into account the size of these large nodes.</li>
<li>LIMDDs [6] store <span class="math-container">$\Theta(n)$</span> bits per edge and can be exponentially more succinct and exponentially faster than other DDs.</li>
<li>the DSDBDD [4,5] will build a BDD for a function <span class="math-container">$f$</span>, and then will do an extra check to see if <span class="math-container">$f$</span> can be written as <span class="math-container">$f(x,y)=g(x)\wedge h(y)$</span>; if so, then it builds BDDs only for <span class="math-container">$g$</span> and <span class="math-container">$h$</span> and discards the (much larger) BDD representing the function <span class="math-container">$f$</span>. This requires more memory per node, but can lead to exponentially smaller and faster diagrams.</li>
</ul>
<p>These tricks fit into a more general patterns where it is admissible to pay a polynomial cost to solve an exponential problem. In these cases there is a &quot;return on investment&quot;. One practical reason why these tricks pay off is that the speed of the operations are heavily influenced by whether the operations cache fits into memory. Indeed, the operations cache can in theory grow to <span class="math-container">$\mathcal O(m^2)$</span> size, if you have <span class="math-container">$m$</span> nodes in your BDD, so in principle it can be the memory bottleneck. Since <span class="math-container">$m^2$</span> items typically doesn't fit in memory (since the <span class="math-container">$m$</span> nodes of the DD almost don't fit into memory), you may have to repeatedly recompute intermediate results, which can take exponential time. By designing a more succinct diagram, you then need a much smaller operations cache, which leads (all other things equal) to a much faster implementation.</p>
<p>When I did my PhD, I got good results by aiming to design new DDs which take advantage of the structure of common Boolean functions (instead of aiming to minimize size per node).</p>
<p><strong>Advice for a software implementation.</strong> Although you did not specifically ask for advice, in your question I read an implicit intention to build a BDD package, so I take the liberty to give some.</p>
<ul>
<li>It may be profitable to stick some extra helper bits onto a node, such as <code>flipped</code> and <code>visited</code>.</li>
<li>design your implementation to be easy to change so that you can easily implement new / additional types of nodes when you have new ideas, and so that you can implement BDD, CBDD, ZDD, etc. without having to write a new implementation from scratch. Microsoft's implementation is actually quite good in this regard. In fact, consider forking their implementation and making your own BDD node a class like their <code>BDD</code> and <code>CBDD</code> nodes.</li>
<li>Find new ways to decompose Boolean functions</li>
</ul>
<p><strong>Why research focuses on the number of nodes.</strong> Let me briefly address why, as you point out, most publications on this topic talk about the number of nodes, not about the byte size of these nodes. They are often trying to find asymptotic bounds on the sizes of DDs, in order to better understand the strengths and weaknesses of different types of DDs (e.g., BDD vs. ZDD vs. SDD). In these situations, considering the size of the node is too granular for the intended purpose, because (i) the size of the node is a multiplicative constant factor, which is absorbed into the <span class="math-container">$\mathcal O(size)$</span> notation, since <span class="math-container">$\mathcal O(size)=\mathcal O((\#nodes)\cdot (size\ per\ node))=\mathcal O(\#nodes)$</span>; and (ii) the margin of error in the size of DD nodes is much smaller than the difference between the sizes of different DDs. For example, in [1], Randall Bryant shows that BDDs have size <span class="math-container">$\mathcal \Omega(2^{n/8})$</span> for a specific function; whereas in [2], Simone Bova shows that SDDs have size only <span class="math-container">$\mathcal O(n^3)$</span>. No matter how efficient your encoding, such a BDD will not fit on disk, but the SDD might fit in memory even with a shoddy implementation.</p>
<p>Having said that, some research is of course done at the granularity of counting bits, e.g., [3] compares several decision diagrams and other methods on the number of bytes needed per state stored, both analytically and empirically.</p>
<p><strong>References</strong></p>
<p>[1] Bryant, Randal E. &quot;Graph-based algorithms for boolean function manipulation.&quot; Computers, IEEE Transactions on 100.8 (1986): 677-691.</p>
<p>[2] Bova, Simone. &quot;SDDs are exponentially more succinct than OBDDs.&quot; Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 30. No. 1. 2016.</p>
<p>[3] Laarman, Alfons. &quot;Optimal compression of combinatorial state spaces.&quot; Innovations in Systems and Software Engineering 15 (2019): 235-251.</p>
<p>[4] Bertacco, Valeria, and Maurizio Damiani. &quot;Boolean function representation based on disjoint-support decompositions.&quot; Proceedings International Conference on Computer Design. VLSI in Computers and Processors. IEEE, 1996.</p>
<p>[5] Vinkhuijzen, Lieuwe, and Alfons Laarman. &quot;The Power of Disjoint Support Decompositions in Decision Diagrams.&quot; NASA Formal Methods Symposium. Cham: Springer International Publishing, 2022.</p>
<p>[6] Vinkhuijzen, Lieuwe, et al. &quot;LIMDD: A decision diagram for simulation of quantum computing including stabilizer states.&quot; Quantum 7 (2023): 1108.</p>

CC BY-SA 4.0
2024-07-05T19:00:41.743Z
2024-07-05T19:00:41.743Z
Lieuwe Vinkhuijzen
<p>You can use adjacency matrices to represent each of these attributes, instead of adjacency lists.</p>
<p>You can consequently use a 2-D array of boolean values to represent these adjacency matrices for the attributes, high, low, value, and auxiliary value.</p>
<p>In general, an adjacency map yields a good trade-off in time and space complexity advantages between adjacency matrices and adjacency lists.</p>
<p>Better factoring/refactoring of the boolean function, like common subexpression elimination in compiler design, would yield more storage savings than optimizing the storage used by each BDD node.</p>
<p>Due to the canonical nature of BDDs, they tend to easily blow up in size. This is overcome by creating better algorithms for BDD optimization, or using another non-canonical data structure (such as AND-inverter graphs, AIG, and Majority-Inverter Graphs, MIGs).</p>

CC BY-SA 4.0
2024-10-17T09:31:12.890Z
2024-10-17T09:31:12.890Z
Giovanni
<p>A straightforward implementation of Binary Decision Diagrams (BDDs) typically requires 12 bytes per node, with an additional 4 bytes commonly used for auxiliary data. Each node is encoded as a 4-tuple with values (hi, lo, value, aux).</p>
<p>Is this memory usage optimal? While researching BDDs, I found numerous papers discussing the theoretical sizes of BDDs (in terms of the total number of nodes) for given circuits. However, there is a lack of information on the specific number of bits needed to encode a single node in a BDD.</p>
<p>Considering that BDDs are a specific type of Directed Acyclic Graph (DAG), this question extends to DAGs in general. What is the optimal bit encoding for nodes in DAGs, and how does this compare to the typical BDD implementation? Are there any known techniques or references that address the encoding efficiency of nodes in DAG structures?</p>
<p>Can anyone provide insights or references on the optimal bit encoding for BDD nodes and DAG nodes in general?</p>

CC BY-SA 4.0
2024-06-24T20:02:23.933Z
What is your reference for the 24 bytes? Also what does "value" stands for? Is it the variable label? 24 bytes may be smaller if the total number of nodes is small as you would not need 8 bytes to encode one pointer. You could be even more succinct by using just the right number of bytes, eg using variable length quantities.
holf
CC BY-SA 4.0
2024-06-25T08:27:55.727Z
Donald Knuth's [BDD14](https://www-cs-faculty.stanford.edu/~knuth/programs/bdd14.w) program uses 32 bytes per node (24 without the ref counter)
[Microsoft's Decsion Diagrams](https://github.com/microsoft/DecisionDiagrams/blob/master/DecisionDiagrams/BDDNode.cs) also uses 24 bytes. 
[Sylvan](https://ris.utwente.nl/ws/portalfiles/portal/6047499/thesis_T_van__Dijk.pdf#subsection.2.2.2), a multi core bdd package uses 16 bytes for each node. Value is the variable's label, also called the variable index.
Taylor Sasser
CC BY-SA 4.0
2024-06-28T08:13:47.917Z
I fail to see how this has anything to do with theoretical computer science. Clearly, the size of encoding of nodes in BDD depends on the size of the data that you want to store in the BDD, and for what purpose. There is nothing in the concept itself that would force you to use any particular node size.
Emil Jeřábek
CC BY-SA 4.0
2024-06-28T08:50:30.137Z
By itself, a BDD with $n$ nodes is a directed acyclic graph where each nonleaf node is labelled with a yes/no query of some kind, and it has two outgoing edges labelled with the two possible answers, whereas each leaf node is labelled with an output value of some kind. Thus, it suffices to have for each node $2\log_2n$ bits + whatever is needed to represent the queries and/or output values. But you mention reference counters and what not, suggesting you want an implementation with additional frills. This is not a matter of theoretical computer science, but of your implementation.
Emil Jeřábek
CC BY-SA 4.0
2024-07-05T19:04:56.557Z
I think this question is a better fit for cs.stackexchange. (How) Should I formally suggest a migration?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2024-07-05T19:35:47.253Z
@LieuweVinkhuijzen There is no open migration path to cs.SE, so the only way is to flag the question for moderator attention.
Emil Jeřábek
<ds.data-structures><it.information-theory><succinct>
Encoding of nodes in Binary Decision Diagrams
Taylor Sasser
# Encoding of nodes in Binary Decision Diagrams

(Asked by: username_0 on 2024-06-21)

A straightforward implementation of Binary Decision Diagrams (BDDs) typically requires 12 bytes per node, with an additional 4 bytes commonly used for auxiliary data. Each node is encoded as a 4-tuple with values (hi, lo, value, aux).

Is this memory usage optimal? While researching BDDs, I found numerous papers discussing the theoretical sizes of BDDs (in terms of the total number of nodes) for given circuits. However, there is a lack of information on the specific number of bits needed to encode a single node in a BDD.

Considering that BDDs are a specific type of Directed Acyclic Graph (DAG), this question extends to DAGs in general. What is the optimal bit encoding for nodes in DAGs, and how does this compare to the typical BDD implementation? Are there any known techniques or references that address the encoding efficiency of nodes in DAG structures?

Can anyone provide insights or references on the optimal bit encoding for BDD nodes and DAG nodes in general?

**Tags:** ds.data-structures, it.information-theory, succinct
> **Comments:**
> **username_1**: What is your reference for the 24 bytes? Also what does "value" stands for? Is it the variable label? 24 bytes may be smaller if the total number of nodes is small as you would not need 8 bytes to encode one pointer. You could be even more succinct by using just the right number of bytes, eg using variable length quantities.  
> **username_0**: Donald Knuth's [BDD14](https://www-cs-faculty.stanford.edu/~knuth/programs/bdd14.w) program uses 32 bytes per node (24 without the ref counter) [Microsoft's Decsion Diagrams](https://github.com/microsoft/DecisionDiagrams/blob/master/DecisionDiagrams/BDDNode.cs) also uses 24 bytes.  [Sylvan](https://ris.utwente.nl/ws/portalfiles/portal/6047499/thesis_T_van__Dijk.pdf#subsection.2.2.2), a multi core bdd package uses 16 bytes for each node. Value is the variable's label, also called the variable index.  
> **username_2**: I fail to see how this has anything to do with theoretical computer science. Clearly, the size of encoding of nodes in BDD depends on the size of the data that you want to store in the BDD, and for what purpose. There is nothing in the concept itself that would force you to use any particular node size.  
> **username_2**: By itself, a BDD with $n$ nodes is a directed acyclic graph where each nonleaf node is labelled with a yes/no query of some kind, and it has two outgoing edges labelled with the two possible answers, whereas each leaf node is labelled with an output value of some kind. Thus, it suffices to have for each node $2\log_2n$ bits + whatever is needed to represent the queries and/or output values. But you mention reference counters and what not, suggesting you want an implementation with additional frills. This is not a matter of theoretical computer science, but of your implementation.  
> **username_3**: I think this question is a better fit for cs.stackexchange. (How) Should I formally suggest a migration?  
> **username_2**: @LieuweVinkhuijzen There is no open migration path to cs.SE, so the only way is to flag the question for moderator attention.  

---

## 2 answers

### Answer by username_3 on 2024-07-05. Score: 4 | Accepted answer

**The minimum size of a BDD node.** A BDD node must contain enough storage for pointers to the low + high nodes, and optionally the variable index. Let's treat these in turn.

* **The `low` and `high` pointers.** The two pointers must each have length $\log\_2(m^\ast)$ if a node can point to $m^\ast$ different other nodes. Here I mean that a node halfway down the diagram cannot point "up", so in principle this pointer only needs to distinguish between the nodes below it. Unfortunately, there is no good way to take advantage of this by achieving an $m^\ast$ which is much smaller than the total number of nodes $m$ in your diagram. To see this, I remark that a completely populated BDD has $2^k$ nodes at layer $k$ (counting from the root), and will have $m^\ast\geq \frac 12m-o(m)$. So unfortunately you cannot save any bits in these pointers by taking advantage of this fact.
* **The variable index.** If only $n$ variables appear in the problems you wish to solve using BDDs, then only $\left\lceil \log\_2(n+1) \right\rceil$ bits are required for the variable index. For example, the [MQT library](https://github.com/cda-tum/dd_package/blob/40dba96ea44a022c855cd2c2c6600a73b8f19059/include/dd/Definitions.hpp) uses a 7-bit index, instead of 32 bits, because its intended use case is problems with up to 128 variables. Indeed, in some BDD versions, each node is connected only to nodes on the next layer, so a variable index is redundant.

**Minimum node size is not the only objective.** Achieving the minimum possible size per node is a good objective. Nevertheless, it is a design choice which is traded off against several other competing objectives that you have when implementing BDD software. The most important other objective is speed: speed is a bottleneck just as often as memory. For example:

* for this reason, many implementations have a `visited` bit on each node, which speeds up operations such as counting the number of nodes in a node's subtree, and counting the number of satisfying assignments (the MQT implementation has this, but Microsoft's does not).
* Many implementations have a `flippped` bit on each node (or each edge), indicating whether the node represents the function $f$ or $\neg f$ (Microsoft's implementation has this).

More broadly, it is admissible to use a different architecture with larger nodes, if that results in a more succinct diagram. For example,

* SDDs have nodes that are unbounded in size, but can be exponentially smaller than BDDs in some cases, even when taking into account the size of these large nodes.
* LIMDDs [6] store $\Theta(n)$ bits per edge and can be exponentially more succinct and exponentially faster than other DDs.
* the DSDBDD [4,5] will build a BDD for a function $f$, and then will do an extra check to see if $f$ can be written as $f(x,y)=g(x)\wedge h(y)$; if so, then it builds BDDs only for $g$ and $h$ and discards the (much larger) BDD representing the function $f$. This requires more memory per node, but can lead to exponentially smaller and faster diagrams.

These tricks fit into a more general patterns where it is admissible to pay a polynomial cost to solve an exponential problem. In these cases there is a "return on investment". One practical reason why these tricks pay off is that the speed of the operations are heavily influenced by whether the operations cache fits into memory. Indeed, the operations cache can in theory grow to $\mathcal O(m^2)$ size, if you have $m$ nodes in your BDD, so in principle it can be the memory bottleneck. Since $m^2$ items typically doesn't fit in memory (since the $m$ nodes of the DD almost don't fit into memory), you may have to repeatedly recompute intermediate results, which can take exponential time. By designing a more succinct diagram, you then need a much smaller operations cache, which leads (all other things equal) to a much faster implementation.

When I did my PhD, I got good results by aiming to design new DDs which take advantage of the structure of common Boolean functions (instead of aiming to minimize size per node).

**Advice for a software implementation.** Although you did not specifically ask for advice, in your question I read an implicit intention to build a BDD package, so I take the liberty to give some.

* It may be profitable to stick some extra helper bits onto a node, such as `flipped` and `visited`.
* design your implementation to be easy to change so that you can easily implement new / additional types of nodes when you have new ideas, and so that you can implement BDD, CBDD, ZDD, etc. without having to write a new implementation from scratch. Microsoft's implementation is actually quite good in this regard. In fact, consider forking their implementation and making your own BDD node a class like their `BDD` and `CBDD` nodes.
* Find new ways to decompose Boolean functions

**Why research focuses on the number of nodes.** Let me briefly address why, as you point out, most publications on this topic talk about the number of nodes, not about the byte size of these nodes. They are often trying to find asymptotic bounds on the sizes of DDs, in order to better understand the strengths and weaknesses of different types of DDs (e.g., BDD vs. ZDD vs. SDD). In these situations, considering the size of the node is too granular for the intended purpose, because (i) the size of the node is a multiplicative constant factor, which is absorbed into the $\mathcal O(size)$ notation, since $\mathcal O(size)=\mathcal O((\#nodes)\cdot (size\ per\ node))=\mathcal O(\#nodes)$; and (ii) the margin of error in the size of DD nodes is much smaller than the difference between the sizes of different DDs. For example, in [1], Randall Bryant shows that BDDs have size $\mathcal \Omega(2^{n/8})$ for a specific function; whereas in [2], Simone Bova shows that SDDs have size only $\mathcal O(n^3)$. No matter how efficient your encoding, such a BDD will not fit on disk, but the SDD might fit in memory even with a shoddy implementation.

Having said that, some research is of course done at the granularity of counting bits, e.g., [3] compares several decision diagrams and other methods on the number of bytes needed per state stored, both analytically and empirically.

**References**

[1] Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.

[2] Bova, Simone. "SDDs are exponentially more succinct than OBDDs." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 30. No. 1. 2016.

[3] Laarman, Alfons. "Optimal compression of combinatorial state spaces." Innovations in Systems and Software Engineering 15 (2019): 235-251.

[4] Bertacco, Valeria, and Maurizio Damiani. "Boolean function representation based on disjoint-support decompositions." Proceedings International Conference on Computer Design. VLSI in Computers and Processors. IEEE, 1996.

[5] Vinkhuijzen, Lieuwe, and Alfons Laarman. "The Power of Disjoint Support Decompositions in Decision Diagrams." NASA Formal Methods Symposium. Cham: Springer International Publishing, 2022.

[6] Vinkhuijzen, Lieuwe, et al. "LIMDD: A decision diagram for simulation of quantum computing including stabilizer states." Quantum 7 (2023): 1108.


---

### Answer by username_4 on 2024-10-17. Score: 0

You can use adjacency matrices to represent each of these attributes, instead of adjacency lists.

You can consequently use a 2-D array of boolean values to represent these adjacency matrices for the attributes, high, low, value, and auxiliary value.

In general, an adjacency map yields a good trade-off in time and space complexity advantages between adjacency matrices and adjacency lists.

Better factoring/refactoring of the boolean function, like common subexpression elimination in compiler design, would yield more storage savings than optimizing the storage used by each BDD node.

Due to the canonical nature of BDDs, they tend to easily blow up in size. This is overcome by creating better algorithms for BDD optimization, or using another non-canonical data structure (such as AND-inverter graphs, AIG, and Majority-Inverter Graphs, MIGs).


---

