TCS -TR-A-13-62

TCS Technical Report

Fast Construction of ZDDs from Large-scale
Hypergraphs
byTakahisa Toda

Division of Computer Science
Report Series A
April 11, 2013

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

toda@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Fast Construction of ZDDs from Large-scale
Hypergraphs
Takahisa Toda
JST ERATO Minato ProjectGraduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060-0814, Japan

April 11, 2013

(Abstract) We present an algorithm to compress hypergraphs into the data structure ZDDs and analyze the computational complexity. Since a ZDD provides anapproach to solve large-scale problems that are diﬃcult to compute in a reasonableamount of time and space, it is important to compress hypergraphs eﬃciently. Ouralgorithm uses multikey Quicksort given by Bentley and Sedgewick. By conducting experiments with various datasets, we show that our algorithm is signiﬁcantly
faster and requires smaller memory than an existing method.

1

Introduction

A hypergraph is a generalization of a graph. While a graph describes an adjacency
relation for two vertices, a hypergraph describes that for any multiple vertices.
Thus a hypergraph is deﬁned to be a pair (V, E) of a set V and a family E of subsets
of V , where the sets in E are called hyperedges. Since a hypergraph can represent
a wide variety of information, there are many applications in computer science.
Recently datasets which are considered as hypergraphs have become widely available. Since such datasets tend to be very large in size, an eﬃcient method tohandle them has become increasingly important.
A zero-suppressed binary decision diagram (ZDD) is a compressed data structure for hypergraphs [9]. Although compression eﬃciency generally depends on
hypergraphs, a ZDD is designed to be eﬀective for sparse hypergraphs, that is, a
hypergraph whose hyperedge sizes tend to be much smaller than the size of a groundset. Sparse hypergraphs often appear in real-life, e.g. as transaction databases. An
advantage of a ZDD is not only compression eﬃciency. The greatest feature is anability to manipulate hypergraphs without explicitly decompressing them. Many
operations including intersection, union and diﬀerence can be eﬃciently performed1

2Takahisa Toda

on ZDDs. As demonstrated in [18],[3] etc, a computation method to construct adesired hypergraph with ZDD operations allows us to solve problems that are diﬃcult to compute in a reasonable amount of time and space in a usual method. It isthus considered as a practically eﬃcient method to handle large-scale hypergraphs.
ZDDs and similar data structure BDDs have been applied to various combinatorial problems. Sekine et al. [17] presented a BDD-based algorithm to compute
the Tutte polynomial of a graph. This algorithm has many applications because
many counting problems in graph theory and related areas are reduced to thiscomputation. For example, it was applied to the exact computation of network
reliability [16]. Coudert [3] advocated a ZDD-based approach to solve graph optimization problems by showing algorithms for three primitive problems to which
many graph optimization problems are reducible. Based on this approach, Knuth
presented an algorithm to compute all minimal hitting sets, as an exercise in his
famous book [8]. The minimal hitting set computation is known to be equivalent to
the dualization of monotone Boolean functions, and there are many applications incomputer science, especially in data mining, logic, and artiﬁcial intelligence (see forexample [4] [5]). Recently, practically fast algorithms for this problem have beendeveloped by many researchers (see [12]). Toda [18] presented a BDD and ZDDbased algorithm for the problem, and experimentally showed that this algorithm
is highly competitive with existing algorithms.
Recently much attention has been paid to the analysis of large-scale databases.
Minato and Arimura [10] proposed a ZDD-based approach for database analysis
problems. Generating frequent itemsets from databases plays an important rolein frequent itemset mining (see [7]). While many generation algorithms have been
proposed, Minato et al. [11] presented a combination of one of the most eﬃcientstate-of-the-art algorithms, called LCM, and ZDDs. This method is called LCM
over ZDDs.
In this paper, we present a fast algorithm to compress hypergraphs into ZDDs.
A naive compression method constructs a ZDD by repeating the union operation
provided in a usual ZDD library (see for example [10][14]). While it is easy to
implement, unfortunately there are some drawbacks on performance. Yet anothermethod is used in the LCM over ZDDs mentioned above. This method constructs
a ZDD in a bottom up fashion while receiving sets successively generated by LCM.
Our algorithm has the same basic principle to LCM over ZDDs, while we further improve it in cooperation with multikey Quicksort, which is a sort algorithm
for strings given by Bentley and Sedgewick [1]. We analyze the computational
complexity of our algorithm. Furthermore, by conducting experimental comparison with various datasets, we show that our algorithm is signiﬁcantly faster andrequires smaller memory than the naive method based on the union operation.
This paper is organized as follows. In Section 2 we introduce the data structure ZDDs. In Section 3 we present an algorithm and analyze the computational
complexity. Section 4 provides experimental results.

3

Fast Construction of ZDDs from Large-scale Hypergraphs



/.-,
()*+
1 ==
=
()*+
/.-,
()*+
/.-,
2 ==
2
=
()*+
/.-,
3 <<<

⊥



>



Figure 1: The ZDD
for the set family{{2, 3}, {1, 3}, {1, 2}}

2





'&%$
!"#
a


/.-,
()*+
b 99
99




⊥

+3



/.-,
()*+
b 44
4


(a) Node elimination



'&%$
!"#
!"#
a PPP '&%$a w PPPP' 
/.-,
()*+
'&%$
!"#
c ;;
b ;;;
;

 

k
 kkkkk'&%$!"#a Pku PP
PPP

P'&%$
' !"#
()*+
+3 /.-,
c ::
b ;;;
:

 

(b) Node sharing

Figure 2: Reduction rules on ZDDs

A Compressed Data Structure for Hypergraphs

Since we use a special data structure for hypergraphs, we provide necessary notions
and results in this section. We identify hypergraphs with set families if the groundset is clear from the context.

2.1

Introduction to ZDDs

A zero-suppressed binary decision diagram (ZDD) is a graph-representation for
hypergraphs. Figure 1 shows an example of ZDD. The node at the top is called
the root. Each internal node has the three ﬁelds V, LO, HI. The ﬁeld V holds anelement in a ground set, where for simplicity we suppose that a ground set consistsof positive numbers. The ﬁelds LO and HI point to other nodes, which are called
LO and HI children, respectively. The arc to a LO child is called a LO arc andillustrated by a dashed arrow, while the arc to a HI child is called a HI arc andillustrated by a solid arrow. There are only two terminal nodes > and ⊥.
For eﬃcient compression, ZDDs satisfy the following two conditions. They must
be ordered : if a node u points to an internal node v, then V (u) < V (v). They
must be reduced : the following two reduction operations can not be applied.
1. For each internal node u whose HI arc points to ⊥, redirect all the incoming
arcs of u to the LO child, and then eliminate u (Fig. 2(a)).
2. For any nodes u and v, if the subgraphs rooted by u and v are equivalent,
then share the two subgraphs (Fig. 2(b)).
We can understand ZDDs as follows. Given a ZDD, each path from the rootto > corresponds to a set in such a way that an element k is included in the set
if a path contains the HI arc of a node with label k; otherwise, k is excluded. For
example, in Fig. 1, the paths 1 99K 2 → 3 → > and 1 → 2 → > correspondto {2, 3} and {1, 2}, respectively. Note that although the node 3 does not appear
in the latter path, the node elimination rule implies that the HI arc of 3 points
to ⊥, and thus 3 must be excluded.

4Takahisa Toda

It is known (see for example [9][8]) that for any ground set V , every hypergraphon V corresponds to a unique ZDD if the order of elements in V is ﬁxed. ZDD nodes
are maintained by a hash table, called a uniquetable, so that for a triple (k, l, h) of
a node label and two ZDD nodes, there is a unique ZDD node p with V (p) = k,
LO (p) = l, and HI (p) = h. Given a triple (k, l, h), the function zdd unique returns
an associated node in the uniquetable if exists; otherwise, create a new node psuch that V (p) = k, LO (p) = l, and HI (p) = h; register p to the uniquetable
and return p. A uniquetable guarantees that two nodes are diﬀerent if and only if
the subgraphs rooted by them represent diﬀerent set families. Thus, for example,
equivalence checking of set families can be done in constant time.

2.2

A Naive Construction Method

We describe a naive algorithm to construct the ZDD for a set family E := {U1 , . . . , Um }on a ground set V . For each set Ui , we construct the ZDD for the set family consisting only of Ui . We then add them by using the union operation. Here the union
operation computes Z(F ∪ G) for Z(F) and Z(G), where Z(S) denotes the ZDD
representing a set family S. As argued in [18], this construction method requires
O(|E| · |V |) time.
Since the union operation is provided in a usual ZDD library, the naive method
is easy to implement, however there are some drawbacks.
• A practical eﬃciency depends on the order to add sets.
• The worst-case time depends on the size of a ground set even if the size of a
set tends to be much smaller than the size of a ground set.
• Many ZDD nodes created during the computation may not appear in an
output ZDD.

3

Algorithm

In this section, we ﬁrst observe that ZDDs are isomorphic to processes of sorting
hyperedges and then present our algorithm.
Figure 3 shows an example of such a correspondence. Suppose that we are
given hypergraph (V, E), where V consists of positive numbers. Each hyperedge
U ∈ E is represented as the array of numbers in U , ordered in increasing order.
The d-th entry of U always means the d-th largest number in U . For the sake ofsimplicity, we assume that every hyperedge contains +∞. We sort all hyperedgesin lexicographical order by recursively partitioning E into the equal part E= andthe greater part E> for the minimum number v at position d of hyperedges. Notethat the following procedure should be initially started with d = 0.
function sort(E, d)5Fast Construction of ZDDs from Large-scale Hypergraphs

s[0]

s[1]

s[2]

s[3]

s[4]

1

2

1

7

9

2

4

4

9

7

7

7

/.-,
()*+
1

(a) The arrays
s[0]

s[1]

s[2]

s[3]

s[4]

s[1]

s[3]

s[4]

s[0]

s[2]

s[3]

s[4]

s[1]

s[2]

s[0]

s[4]

s[3]


w
/.-,
()*+
/.-,
()*+
2
2


 ()*+| ()*+
/.-,
()*+
()*+
7 /.-,
4 /.-,
4 /.-,
7
 ()*+
()*+
/.-,
()*+
()*+
9 FF/.-,
7
9 77 /.-,
7 /.-,FF 7

FF7
F" 7   w+∞(c) The binary tree representation

/.-,
()*+
1 JJJ
JJ
$
xV
()*+
/.-,
()*+
/.-,
2 VVVVV
2
VVVV 
VV/.-,
*4
()*+



()*+
/.-,
7

 



*9
/.-,
()*+

 |
⊥

()*+
/.-,
7

" 
>

(d) The reduced ZDD(b) The sorting process, ordered from right to left

Figure 3: The process of sorting s[0], . . . , s[4] and the corresponding ZDD.
if |E| ≤ 1 thenreturn;end ifv ← the minimum number among the d-th entries of sets in E;
if v = +∞ thenreturn;end if
E= ← the set of hyperedges with the d-th entries equal to v;
E> ← E \ E= ;sort(E= , d + 1); sort(E> , d);end function
The sorting process can then be represented as an ordered binary tree such thateach node holds a partitioning number v; the left and the right children of a nodecorrespond to E> and E= , respectively. When we consider the left and the rightchildren of a node as the LO and the HI children, this binary tree satisﬁes theorder condition of ZDD nodes, and furthermore it is irreducible with respect tothe node elimination rule, because v < +∞ implies E= 6= ∅. Note that all recursivefunction calls exactly correspond to the nodes in this tree. By sharing equivalentsubgraphs, we obtain the corresponding ZDD. It would be easy to observe that
this correspondence is bijective.
This sort algorithm has a close relation to the ternary partitioning algorithm,
called multikey Quicksort, given by Bentley and Sedgewick [1]. Their algorithm
sorts strings in a similar way, but there are two diﬀerent points. Firstly, a partitioning number v need not be the minimum number and there are many ways forthe choice, from computing the true median to choosing a random value. Secondly,

6

Takahisa Toda

it partitions E into the three parts E< , E= and E> , where E< , E= and E> consists ofhyperedges with the d-th entries smaller than, equal to and greater than v, respectively. An eﬃcient partitioning method is important. The performance of multikey
Quicksort is well-analyzed. We extract the following two theorems from [1], wherec denotes a constant. A worst-case and an expected-time algorithms that establish
c = 3 and c = 3/2 are given in [15] and [6], respectively.
Theorem 1. If multikey Quicksort partitions around a median computed in cn
comparisons, it sorts n k-vectors in at most cn(log n + k) scalar comparisons.
Let Hn denote the harmonic numbers, deﬁned by Hn =∑1≤i≤n 1/i.

Theorem 2. A multikey Quicksort that partitions around the median of 2t + 1
randomly selected elements sorts n k-vectors in at most 2nHn /(H2t+2 − Ht+1 ) +O(kn) expected scalar comparisons.
When we sort sets with multikey Quicksort, the worst-case number of comparisons does not depend on the size of a ground set. Thus it would be eﬀective if asparse set family is given. However, since multikey Quicksort is based on a ternary
partitioning method, it is isomorphic to ternary search trees and does not lead to
ZDDs directly.
In view of the observation above, our idea is that we ﬁrst sort sets with multikey
Quicksort and then construct a ZDD, based on the binary partitioning method.
Algorithm 1 shows the construction part. Since an input set family E is alreadysorted, ﬁnding the minimum number v and partitioning E into E= and E> can bedone quickly: since the hyperedges with the d-th entries equal to v are all lined up
from the beginning and we need not search all hyperedges.
Algorithm 1 Compute the ZDD for a set family E.
function zcomp(E, d)
if E = ∅ thenreturn ⊥;end ifv ← the minimum number among the d-th entries of sets in E;
if v = +∞ thenreturn >;end if
E= ← the set of hyperedges with the d-th entries equal to v;
E> ← E \ E = ;hi ← zcomp(E= , d + 1); lo ← zcomp(E> , d);return zdd unique(v, lo, hi);end function
Theorem 3. Suppose that an input set family E is given as an array of hyperedges sorted in lexicographical order. Algorithm 1 can be implemented to run inFast Construction of ZDDs from Large-scale Hypergraphs7∑
O(N log2 ( U ∈E |U |/N )) time, where N denotes the number of nodes in the binary
tree that is obtained from an output ZDD by not sharing equivalent subgraphs. The
required space is proportional to the size of an output ZDD.
Proof. Since E is already sorted, in order to partition E to E= and E> , it is suﬃcient
to ﬁnd the last hypergraph whose d-th entries equals v. This can be eﬃciently doneby skipping as many hypergraphs as possible. Consider for example the following
procedure.
1. Let the current hypergraph be the ﬁrst one.
2. Search only the 2i -th hypergraphs from the current hypergraph for i =1, 2, · · · while the d-th entries equal v.
3. If the last hypergraph is not found, then go to the 2nd step.
4. Return the last hypergraph.
Since the 2nd step is over in at most log |E= | steps, the overall procedure requires
O(log2 |E= |) time. Since the d-th entries equal to v are not examined in laterrecursive calls, the sum of all the sizes |E= | equals the sum of all hyperedge sizes.
∑
From Jensen’s inequality, it follows that the total time is O(N log2 ( U ∈E |U |/N )).
Since Algorithm 1 constructs an output ZDD in a bottom up fashion, all nodes
requested by zdd unique appear in the output ZDD. Note that since the maximum
depth of a recursive function call corresponds to the maximum length of a path inan output ZDD, it is clear that the space required to keep track of the recursivefunction calls is dominated by an output ZDD size.

4

Experiment

Implementation and Environment. We implemented our algorithm and the naive
method presented in Section 2.2 in C. We furthermore implemented the combination of multikey Quicksort and the naive method, in which an input data ﬁle issorted with multikey Quicksort and then the naive method is executed. In these
programs, we used the BDD Package Sapporo-Edition-1.0 developed by Minato,in which ZDDs are available and various basic operations for ZDDs are provided.
The (non-tuned) implementation of multikey Quicksort was obtained from [2]. All
experiments were performed on a 2.67GHz Xeon R E7-8837 with 1.5TB RAM, running SUSE Linux Enterprise Server 11. We compiled our code with version 4.3.4of the gcc compiler.
Problem Instances. The following instances were obtained from the HypergraphDualization Repository [13], where n denotes an instance parameter.

8Takahisa Toda

• BMS-WebView-2 (bms(n)): a hypergraph such that the size of a ground set
is 3,341 and each hyperedge is the complement of a set of maximal frequent
itemsets with support threshold n, of datasets “BMS-WebView2” taken fromthe Frequent Itemset Mining Dataset Repository.
• Uniform random (rand(n)): a hypergraph such that the size of a ground set
is 50 and the number of hyperedges is 1,024,000 and each vertex is included
in a hyperedge in the probability n/10, generated by Prof. Alain Bretto.
The following instances were obtained from the Frequent Itemset Mining Dataset
Repository.
• T40I10D100K: this data set was generated using the generator from the IBM
Almaden Quest research group.
• retail: this dataset contains the (anonymized) retail market basket data froman anonymous Belgian retail store, donated by Tom Brijs.
• accidents: this dataset contains (anonymized) traﬃc accident data, donatedby Karolien Geurts.
We furthermore generated instances of the following type.
• Threshold function (TH(n)): a hypergraph whose hyperedges correspond toprime conjunctive normal forms of the threshold function with 30 variables(that)returns 1 if at least n variables are 1. The number of hyperedges is30
n−1 .
All instances are given as data ﬁles with the following format: each row corresponds to a hyperedge, and entries are non-zero positive numbers (and less thanor equal to the maximum number allowed in a BDD package); the entries in a row
are sorted in increasing order and separated by a white space. Since some data
sets obtained from the Frequent Itemset Mining Dataset Repository did not havea correct form, we formated them: in particular all entries are incremented by one
so that they are positive.
Comparison of Algorithms We compared our algorithm zcomp, the naive method,
and the combination of multikey Quicksort and the naive method. Note that zcomp
means the combination of multikey Quicksort and Algorithm 1. In this experiment,
the rows in data ﬁles were rearranged at random. The results are shown in Fig. 4
and Table 1.

5

Conclusion

We presented a new algorithm for constructing ZDDs for hypergraphs. This algorithm sorts hyperedges with multikey Quicksort and then construct a ZDD in9Fast Construction of ZDDs from Large-scale Hypergraphs

500

70
zcomp
sort+naive
naive

450

maximum memory [G byte]

time [sec]

350
300
250
200
150
100

50
40
30
20
10

50
0

0
0

2

4
6
threshold function

8

10

0

50
zcomp
sort+naive
naive

4
6
threshold function8

6
7
Uniform Random

8

10

zcomp
sort+naive
naive

8
Maximum memory [G byte]

40
35
time [sec]

2

9

45

30
25
20
15
10

7
6
5
4
3
2
1

5

0
3

4

5

6
7
Uniform Random

8

9

10

3

400

70

300
250
200
150
100
50
0
1000

4

5

9

10

80
zcomp
sort+naive
naive
Maximum memory [G byte]

350

time [sec]zcomp
sort+naive
naive

60

400

zcomp
sort+naive
naive

60
50
40
30
20
10

100
BMS-Web-View-2

10

0
1000

100
BMS-Web-View-2

10

Figure 4: Comparison of running time and maximum memory usage, where thehorizontal coordinate of a point represents an instance parameter n.
a bottom up fashion. We analyzed the computational complexity of the construction part. We furthermore conducted experiments with various datasets. The
experiments showed that our algorithm is signiﬁcantly faster and requires smaller
memory than an existing method.

References[1] J. Bentley and R. Sedgewick. Fast algorithms for sorting and searching strings.
In 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 360–369,
New Orleans, Louisiana, USA, January 1997.
[2] J. Bentley and R. Sedgewick. Fast algorithms for sorting and searching strings.
http://www.cs.princeton.edu/~rs/strings/, 2013. accessed on 7 April.
[3] O. Coudert. Solving graph optimization problems with ZBDDs. In the1997 European Conference on Design and Test, pages 224–228, Paris, France,
March 1997.

10

Takahisa Toda

Table 1: Comparison of running time and maximum memory usage

T40I10D100K
retailaccidents

naive
7.32
15.59
19.36

time (sec)
sort+naive
7.53
18.85
18.43

zcomp
2.53
0.34
3.84

naive
2.00
4.18
4.19

memory (G byte)
sort+naive
2.07
4.42
4.39

[4] T. Eiter and G. Gottlob. Hypergraph transversal computation and related
problems in logic and AI. LNAI, 2424:549–564, 2002.
[5] T. Eiter, K. Makino, and G. Gottlob. Computational aspects of monotone
dualization: A brief survey. Discrete Applied Mathematics, 156:2035–2049,
2008.
[6] R. Floyd and R. Rivest. Expected time bounds for selection. Communicationsof the ACM, 18(3):165–172, 1975.
[7] B. Goethals. Survey on frequent pattern mining. http://win.ua.ac.be/~adrem/bibrem/pubs/fpm_survey.pdf, 2003.
[8] D. Knuth. The Art of Computer Programming Volume 4a. Addison-Wesley
Professional, New Jersey, USA, 2011.
[9] S. Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In 30th ACM/IEEE Design Automation Conference (DAC-93), pages
272–277, Dallas, Texas, USA, Jun 1993.
[10] S. Minato and H. Arimura. Eﬃcient method of combinatorial item set analysis
based on Zero-Suppressed BDDs. In IEEE/IEICE/IPSJ International Workshop on Challenges in Web Information Retrieval and Integration (WIRI2005), pages 3–10, Tokyo, Japan, April 2005.
[11] S. Minato, T. Uno, and H. Arimura. LCM over ZBDDS: fast generation ofvery large-scale frequent itemsets using a compact graph-based representation.
In 12th Pacific-Asia conference on Advances in knowledge discovery and data
mining, pages 234–246, Osaka, Japan, May 2008.
[12] K. Murakami and T. Uno. Eﬃcient algorithms for dualizing large-scale hypergraphs. In Proc. of the Meeting on Algorithm Engineering & Experiments(ALENEX), pages 1–13, New Orleans, Louisiana, USA, January 2013.
[13] K. Murakami and T. Uno. Hypergraph dualization repository. http://research.nii.ac.jp/~uno/dualization.html, 2013. accessed on 19 January.

zcomp
0.63
0.16
1.19

Fast Construction of ZDDs from Large-scale Hypergraphs

11[14] A. Salleb and C. Vrain. Estimation of the density of datasets with decision
diagrams. In M.-S. Hacid, N. Murray, Z. Raś, and S. Tsumoto, editors, Foundations of Intelligent Systems, volume 3488 of Lecture Notes in Computer
Science, pages 688–697. Springer Berlin Heidelberg, 2005.
[15] A. Schoenhage, M. Paterson, and N. Pippenger. Finding the median. Journalof Computer and Systems Sciences, 13:184–199, 1976.
[16] K. Sekine and H. Imai. A uniﬁed approach via BDD to the network reliability
and path number. Technical Report TR-95-09, Department of Information
Science, University of Tokyo, 1995.
[17] K. Sekine, H. Imai, and S. Tani. Computing the tutte polynomial of a graphof moderate size. In 6th International Symposium on Algorithms and Computations, pages 224–233, Cairns, Australia, December 1995.
[18] T. Toda. Hypergraph transversal computation with binary decision diagrams.
In 12th International Symposium on Experimental Algorithms, Rome, Italy,
June 2013. accepted.