## 4 Examples  
In this section we provide two examples. First, we applied our algorithm to two datasets commonly used in frequent itemset mining. The datasets we used are mushroom and pumsb obtained from the Frequent Itemset Mining Dataset Repository. The mushroom dataset contains characteristics of various species of mushrooms and the pumsb dataset contains census data for population and housing. In both datasets, each record consists of distinct item IDs, which indicate characteristics of the record. Each record is considered as a set of items and a dataset as a set family, thus both datasets can be represented as ZDDs (see Table 1). The parameters \(n\) and \(k\) given in Theorem 3.2 correspond to the number of distinct items that appear in a dataset and the maximum number of items in a record, respectively. Although the maximum item ID in the pumsb dataset is 7116 and the minimum item ID is 0, there are only 2113 distinct item IDs. Thus we normalized the ground set to be the set \(\{1,2,\ldots,2113\}\) such that each element \(i\) in the set corresponds to the \(i\)-th item ID that appears in the pumsb dataset. The computed partitions for the mushroom and the pumsb datasets are shown in Table 2, where the entries in the right table are shown as original pumsb item IDs. For example, in each record of \begin{table}
\begin{tabular}{r r r r r r r} \hline  & **\#Records** & **\#Items (\(n\))** & \(k\) & \(m\) & \(n+km\) & **\#ZDD Nodes** \\ \hline mushroom & 8,124 & 119 & 23 & 288 & 6,743 & 791 \\ pumsb & 49,046 & 2,113 & 74 & 48,058 & 3,558,405 & 1,498,636 \\ \hline \end{tabular}
\end{table} 
Table 1: The used datasets, where \(n,k,m\) denote the parameters given in Theorem 3.2.  
the mushroom dataset, either elements 75 and 89 both appear or none of them do. Since items in the same block have the same behavior, when we want to find useful information from a ZDD, we need not distinguish between them. If the number of blocks is small, then various analyses on a ZDD can be efficiently performed on a small set of items by selecting one representative from each block. Thus our algorithm is useful. Unfortunately, without any constraints there are many blocks in both datasets; however, a few constraints may reduce the number of blocks significantly. For example, in the pumsb dataset, there are 2037 many blocks without any constraints, while the constraints \(\mathrm{ON}=\{5065\}\) and \(\mathrm{OFF}=\emptyset\) reduce the number to \(71\) (see Table 3 for other settings of constraints). As a second example, we applied the algorithm for the conditional case to a set of paths enumerated from the graph given in Figure 6. We considered paths from the vertex \(01\) to the vertex \(47\) of the graph such that no vertices are visited twice, which are called simple paths. Since simple paths can be identified with sets of edges, the set of all simple paths from \(01\) to \(47\) can be represented as a ZDD whose ground set corresponds to the edge set of the graph. The number of such simple paths turns out to be 14,144,961,271, while the corresponding ZDD in our ordering of the edge set has only 599 branch nodes (see Table 4). This is in contrast to the pumsb dataset in the previous example, where the number of branch nodes is roughly the same as the number of records represented by a ZDD. The ZDD of the  
\begin{table}
\begin{tabular}{c c  
present example can be quickly constructed in a top-down fashion. This technique has been described in the literature; see, e.g., [5; 12], (Exercise 225 in SS7.1.4). We analyzed which edges co-occur with each other for all simple paths with the constraints \(\mathrm{ON}\) and \(\mathrm{OFF}\) given in Figure 6. The computed partition is shown in the right table of Figure 6. As we showed in Theorem 3.3, once we obtain a small ZDD like in this case, we can quickly compute co-occurrence partitions in various settings of \(\mathrm{ON}\) and \(\mathrm{OFF}\).