TCS -TR-A-13-63

TCS Technical Report

Z-Skip-Links for Fast ZDD Traversal
in Handling Large-Scale Sparse DatasetsbyShin-ichi Minato

Division of Computer Science
Report Series A
April 25, 2013

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Z-Skip-Links for Fast ZDD Traversal
in Handling Large-Scale Sparse Datasets
Shin-ichi Minato∗
Division of Computer Science
Hokkaido University
Sapporo 060-0814, Japan

April 25, 2013

(Abstract) ZDD (Zero-suppressed Binary Decision Diagram) is known as an efﬁcient data structure for representing and manipulating large-scale sets of combinations. In this article, we propose a method of using Z-Skip-Links to accelerate
ZDD traversals for manipulating large-scale sparse datasets. We discuss averagecase complexity analysis of our method, and present the optimal parameter setting. Our method can be easily implemented into the existing ZDD packages justby adding one link per ZDD node. Experimental results show that we obtained
dozens of acceleration ratio for the instances of the large-scale sparse datasets
including thousands of items.

1

Introduction

A set of combinations is one of the most fundamental model of discrete structure forsolving combinatorial problems in various applications. Binary Decision Diagram(BDD) [2], a state-of-the-art data structure of Boolean function representation,is sometimes used for solving combinatorial problems because n-input Booleanfunctions have one-to-one correspondence to the sets of combinations consideringn items. Zero-suppressed BDD (ZDD) [9] is a variant of BDD, customized for
manipulating sets of combinations. ZDDs have been successfully applied not only
for VLSI design but also for various real-life applications, such as data mining,system diagnosis, and network analysis.
Recently, processing of “Big Data” have attracted a great deal of attention, and
we often deal with a large-scale sparse dataset, which has more than thousand or
ten thousands of items as the columns of a dataset. If we represent such data using
a ZDD, the height of ZDD grows as large as the number of items, and the depth∗
He also works for ERATO MINATO Discrete Structure Manipulation System Project, Japan
Science and Technology Agency.

1

2

Shin-ichi Minato

Figure 1: Binary Decision Tree, BDD and ZDD.

of recursive operations also becomes very large. Thus, ZDD-based manipulation isusually not very eﬃcient for such large-scale sparse datasets.
In this paper, we propose an idea of attaching a “Z-Skip-Link” to each ZDD node
for accelerating the traversal of ZDDs of large-scale sparse datasets. It consumes
only a constant size of additional memory, and can easily be implemented into a
conventional BDD/ZDD package. We also show the average-case computation timeof traversing ZDDs, in order to evaluate the eﬀect of Z-Skip-Links and thier optimal
setting of the skip length. In the practical case of sparse datasets with thousandsof items, our experiments show that the use of Z-Skip-Links makes the membership
operations 10 to 30 times faster than using conventional ZDD operations.
In the rest of this paper, we ﬁrst explain the basic properties of ZDDs and whatis the problem in manipulating large-scale sparse datasets. We then present anidea of Z-Skip-Links and average-case complexity analysis. Finally we describe thealgorithm implementation and the experimental results.

2

Preliminary – Basic Properties of ZDDs

A Binary Decision Diagram (BDD) [2] is a graph representation for a Booleanfunction. As illustrated in Fig. 1, it is derived by reducing a binary decision tree,
which represents a decision making process that depends on some input variables.
In this graph, we may ﬁnd the following two types of decision nodes:(a) Redundant node: A decision node whose two child nodes are identical.
(b) Equivalent nodes: Two or more decision nodes having the same variable andthe same pair of child nodes.
If we ﬁnd such types of nodes, we can reduce the graph without changing thesemantics (in other words, we can compress the graph). If we ﬁx the order of input
variables and apply the two reduction rules as much as possible, then we obtain acanonical form for a given Boolean function [1]. Such a data structure is called an
Ordered BDD (OBDD), but in this article we will just call it a BDD.

Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets

3

Figure 2: ZDD reduction rule.

The compression ratio of a BDD depends on the properties of Boolean function
to be represented, but it can be 10 to 100 times more compact in some practicalcases. In addition, we can systematically construct a BDD that is the result of abinary logic operation (i.e., AND or OR) for a given pair of BDDs. This algorithm
is based on a recursive procedure with hash table techniques, and it is very eﬃcientwhen the BDDs have a good compression ratio. The computation time is boundedby the product of the BDD sizes of the two operands, and in many practical cases,
it is linearly bounded by the sum of input and output BDD sizes [12].
Zero-suppressed BDDs (ZDDs, or ZBDDs) [9] are a variant of BDDs, customized
to manipulate sets of combinations. An example is shown in Fig.1. ZDDs are basedon special reduction rules that diﬀer from the ordinary ones. As shown in Fig. 2,
we delete all nodes whose 1-edge directly points to the 0-terminal node, but do notdelete the nodes which would be deleted in an ordinary BDD. Similarly to ordinary
BDDs, ZDDs give compact canonical representations for sets of combinations. We
can construct ZDDs by applying algebraic set operations such as union, intersection
and diﬀerence, which correspond to logic operations in BDDs.
The zero-suppressing reduction rule is extremely eﬀective if we are handling a
set of sparse combinations. If the average appearance ratio of each item is 1%,
ZDDs are possibly up to 100 times more compact than ordinary BDDs. Suchsituations often appear in real-life problems, for example, in a supermarket, thenumber of items in a customer’s basket is usually much less than the number of
all the items displayed.
Recently, ZDD has become more widely known, since D. E. Knuth intensively
discussed ZDD-based algorithms in the latest volume of his famous series of books[6]. The original BDD was invented and developed for VLSI logic design, but ZDD
is now recognized as the most important variant of BDD, and is widely used invarious kinds of problems in computer science [3, 7, 8, 5].

4Shin-ichi Minato(a) Large-scale sparse dataset.

(b) ZDD

Figure 3: Large-scale sparse dataset and ZDD.

3

Problem for Handling Large-Scale Sparse Datasets

Recently, some kinds of Big Data are regarded as a large-scale sparse dataset, which
is a set of many combinations each of which selects a few items out of thousands ofones, as illustrated in Fig. 3(a). There are so many practical examples, such as thebasket data in a supermarket, the word-correlation dataset in a natural language,
the key word lists in document database, grouping of Internet web pages, and SNPs
(mutation points) of human gene data.
If we represent such a large-scale sparse dataset using a ZDD, each path from theroot node to the 1-terminal node corresponds to one combination in the dataset,as shown in Fig. 3(b). Namely, the number of such paths in the ZDD equals thenumber of combinations in the dataset, and the 1-edges on each path represent theoccurrence of items in a combination. Since the zero-suppression rule automaticallydeletes the ZDD nodes corresponding to the items not occurring in the combination,
the ZDD size is bounded by the total number of item occurrences in the datasets. If
there are many partially similar patterns of combinations, the paths in the ZDD areshared with each other, and in such cases very large compression ratio is obtained.
For example, LCM-ZDD method [10] eﬃciently generates nearly a billion patterns
of frequent itemsets by using only thousands of ZDD nodes.
Such data compression is one of the big advantage of using ZDDs, however,there is a hidden problem that the height of the ZDD must be n if the dataset
contains n relevant items. If we represent a large-scale and sparse dataset using
thousands of items, the ZDD becomes a very unbalanced form as shown in Fig. 4,
such that we need more than thousand hops for 0-edge traversal while only a few
hops needed for 1-edge side to reach a terminal node. Unfortunately, such type ofdatasets often appear in real-life applications. In general, ZDD-based operations
require a computation time linear in the height of the ZDD. The membership
testing operation is especially ineﬃcient in this case because thousands of steps of
ZDD traversal is needed to check the existence of the k-th item’s decision node,even if the membership query has only a combination with a few items. It means

Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets

Figure 4: An example of very unbalanced ZDD.

5

Figure 5: ZDD with Z-Skip-Links.

that the ZDD-based operation could be hundreds or more times slower than a naive
data structure based on arrays and linked lists.
In this paper, we propose a practical method for addressing this problem forhandling large-scale sparse datasets using ZDDs.

4

Z-Skip-Links

4.1

Basic Idea

Conventional ZDD operation linearly traverses the cascade of 0-edges, and it requires O(n) steps in average to check the existence of a ZDD node with a given item
where n is the height of the very unbalanced ZDD. If we prepare a table of pointersto the descendant ZDD nodes indexed by the item IDs, we can directly jump to
the destination node in O(1) steps. However, we have to prepare such a pointertable for each ZDD nodes as the start point, so additional memory requirement
becomes O(n) words per ZDD nodes, and the total memory requirement becomesO(nG), where G is ZDD size. This is unacceptable memory increase for large n as
hundreds or thousands.
Our basic idea is to attach only one pointer to each ZDD node, as illustrated
in Fig. 5. The pointer, named Z-Skip-Link, indicates a descendant node reachable
by a some length of cascade of 0-edges. When we want to search a ZDD nodewith the t-th level, we ﬁrst refer the Z-Skip-Link at the root node and check thelevel of the pointed node s. If s is still higher than t, we execute the jump by the
Z-Skip-Link and continue the search from there. If s is exceedingly lower than t,
we cancel the jump and descend the 0-edges for one step, and then continue thesearch at the next node.
Our method is quite simple, but the reachability is clearly guaranteed as ordinary linear search. The search time can be reduced as much as the total jump

6Shin-ichi Minato

Figure 6: Basic Model with a Number Line.

length of Z-Skip-Links. The additional memory requirement is just a constantfactor for the ZDD size. Since the Z-Skip-Links do not have any side-eﬀect to the
ZDD operations, we can easily implemented in a conventional BDD/ZDD package without any signiﬁcant modiﬁcation to the basic data structure and operation
codes.
The key issue of this method is the design of the skip length of Z-Skip-Links.
The longer skip length gets the more saving time, but too longer skip length may
increase the probability of exceeding the target and the less chance of speed up.
In this article, we discuss the average case analysis of time complexity and the
optimal skip length for a given n.

4.2

Basic Model and Average Search Cost

For analyzing average search cost, we consider the model of a number line as shownin Fig. 6. There are n positions on the line from 1 to n, where the start position isn, and the target position is t. We deﬁne a skip length function J(x) to represent
the skip length at the current position x (1 ≤ x ≤ n). The ﬁrst skip length shouldbe J(n) and the second length becomes J(n − J(n)). We repeat the jumps until
passing through the target t, and after that we execute a linear search from thelast position. In this model, we do not know t beforehand, thus we assume that t
has a discrete uniform distribution between 1 to n. Here, we deﬁne C1 (n) as theaverage number of jumps, and C2 (n) as the average number of moves in the linear
search. Our objective is to design a good skip length function J(x) to minimize
the total average cost C(n) = C1 (n) + C2 (n). The function J(x) cannot depend
on t but may depend on n.
At ﬁrst, we assume the simple skip length function with a constant α ≥ 1:J(x) =


1
x .
α

(1)

For example, α = 4 means that we skip 1/4 distance of the remaining searchrange. Then, we get the average search cost C(n) as follows. (Detailed calculationis shown in Appendix.)C(n) = α +n4(α − 2)(2)

Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets

7

Figure 7: Two-Phase Model.

If we set α = 16, we get C(10000) ≈ 182.6, which is 27.4 times faster than ordinary
linear search.
Let us consider the optimal α for a given n. The derivative of C(n) with respect
to α can be written as:dnC(n) = 1 −dα4(α − 2)2
and it becomes zero, thus:nαopt =+ 2, Copt (n) = n + 2
2

(3)

√
n
are obtained. In other words, we can accelerate up to 2 times in average fromlinear search. When n = 10000, we get αopt = 52 and Copt (10000) = 102, about
50 times faster than linear search.

4.3

Two-Phase Model

The above discussion assumed a uniform skip length function, but we may improve
the performance if we use diﬀerent forms of skip length functions for diﬀerent
positions. Figure 7 illustrates our idea of the two-phase model, using the two
types of skip length functions J1 (x) and J2 (x) for an even number x and an odd
number x, respectively. J1 (x) provides long jumps and J2 (x) provides middle
length jumps. We ﬁrst repeat long jumps with J1 (x) until passing through thetarget t, next we repeat middle jumps with J2 (x), and after that we execute alinear search. We set that both J1 (x) and J2 (x) return an even number of skip
length, and thus destination of J1 is always a position of J1 , and J2 also going toa J2 position.
We also analyzed the average case search cost in this two-phase model. We
assume the same skip length as 1/α of remaining search range for both J1 (x)and J2 (x). Then C(n) is described as follows. (Detailed calculation is shown inAppendix.)C(n) = 2α +n8(α − 2)2

(4)

8

Shin-ichi Minato

If we set α = 16, we get C(10000) ≈ 38.4, which is about 130 times faster thanordinary linear search.
Similarly to the uniform model, we can calculate optimal α for a given n.
3αopt =n+ 2,
2Copt (n) =

3
3
n+4
2

(5)

When n = 10000, we get αopt = 21.54 and Copt (10000) ≈ 36.3, about 138 times
faster than linear search.
In the above discussion, we ignored at most 2 steps which are required forchanging J1 and J2 positions, so we must add a small constant factor for exact
analysis. Anyway, we can signiﬁcantly improve the performance only using two
diﬀerent skip length functions without any additional memory requirement.

4.4

k-Phase Model

Extending the two-phase model, we can consider k types of skip length functions,by classifying the position x into k groups by x modulo k. If we write C (k) (n) for
the average search cost for k-phase model, it can be described as:
C (k) (n) = kα +n(6)

2k+1 (α − 2)kand optimal α is obtained as:
1 1
αopt = n k+1 + 2,2(k)Copt (n) =1
k + 1 k+1
+ 2k
n
2

(7)

For example, when k = 4, we get
αopt =1
5
n + 2,
2(4)

Copt (n) =5
5
n + 8.
2(8)

Next, let us consider the optimal k for given n. The detailed calculation isshown in Appendix and we can obtain the following result.
(k)

kopt = ln n − 1, Coptopt (n) =5ln n − 22(9)Consequently, the average search cost of the Z-Skip-Links is theoretically shownas O(log n), if we use optimal k.
(10)

In the case of n = 65536, we get kopt ≈ 10 and Copt (65536) ≈ 25.6. However,(4)even for k = 4 we can achieve Copt (65536) ≈ 30.97, which is more than 1000 times
faster than ordinary linear search. We can conclude that, for up to n = 100000,
4-phase model is suﬃciently eﬀective for practical applications.

Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets

400
350
300
250
200
150
100
50
0

9

C(n)
(1/16) x
2 sqrt(x)2-layer4-layer
n
0

20000

40000

60000

80000

100000 120000

Figure 8: Computational Experiments.

Figure 9: An Example of Skip List [11].

4.5Computational Experiments

To conﬁrm the above theoretical analysis, we conducted computational experiments. For a given n, we counted the number of moves to t, and computed average
moves C(n) for all t from 1 ton. In this experiments we tested four kinds of1
skip length functions as 16
x, 2 x, the optimal 2-phase model, and the optimal
4-phase model. Figure 8 shows the results. We can observe the result very close
to theoretical formulas up to n = 100000.

4.6

Related Work

Our method is related to Skip List proposed by Pugh [11] in 1990. Skip List isa quick access technique used for sorted linear linked list. It equips probabilistic
distributed skip pointers as shown in Fig. 9. It is known that the average accesstime is O(log n). From this viewpoint, Z-Skip-Links can be regarded as a kindof Skip List technique deterministically attached to all ZDD nodes. However, ourmethod is not limited a simple linear list but applicable to the complex ZDD
structure including a large number of paths shared with each other.

5

Algorithm Implementation

5.1

Implementation to Conventional BDD/ZDD Package

Most of conventional BDD/ZDD packages use short int (16 bit integer) for item
IDs, so we assumed up to n = 65535. For this range, we know that 4-phase10Shin-ichi Minato

Table 1: Look-up Table for Skip Length Function.
range of x J1 (x) J2 (x) J3 (x) J4 (x)5 − 154−−−
16 − 6384−−
64 − 255641684
256 − 511
128
32
8
4
512 − 1023
256
64
16
4
1, 024 − 2047
512
128
32
8
2, 048 − 4095 1,024
256
64
8
4, 096 − 8, 191 2,048
512
648
8, 192 − 32, 767 4,096
512
64
8
32, 768 − 65, 535 8,192 1,024
128
16

is enough eﬀective, so we adopted the 4-phase model. It is time consuming to5calculate n many times, so we approximate it by table look-up. The table isshown in Table. 1
Also, Most of conventional BDD/ZDD Packages have an internal table called“operation cache,” which stores the recent operations and their results by a hashkey with the pointers to the operand ZDDs and operation IDs. Our Z-Skip-Links
can be easily implemented using the framework of the operation cache, and we
needed only 100 lines of additional C++ codes for processing Z-Skip-Links.
Here we explain the algorithm of fast ZDD traversal using Z-Skip-Links, andthe preprocessing algorithm for constructing Z-Skip-Links for all ZDD nodes.

5.2

ZDD Traversal Using Z-Skip-Links

Figure 10 shows pseudo codes of ZDescend(F, t). For given root node of ZDD F
and the target item-ID t, this algorithm returns the pointer to a ZDD node whichis the ﬁrst meet such that the item ID is equal or lower than t when descending
0-edges starting from F . In this codes, cache(”ZSkip at F ”) means to refer theoperation cache. This algorithm enjoys the beneﬁt of Z-Skip-Links, however, even
if Z-Skip-Lists are not prepared yet, it returns correct result by linear search.

5.3

Construction of Z-Skip-Links

Figure 11 shows pseudo codes of SetZSkip(F ). This algorithm constructs Z-SkipLinks for all internal nodes of ZDD F by using a recursive procedure. At ﬁrst, we
check the operation cache and if a Z-Skip-Link is already constructed, the procedureterminates. Otherwise, recursively call itself with the 0-child node to construct ZSkip-Links for all descendant nodes. After that, compute the skip length and ﬁnd
the destination node by using ZDescend procedure, and then register it to theoperation cache.
The number of recursive call of SetZSkip is bounded by the number of F ’s ZDD
nodes if operation cache works well. SetZSkip also calls ZDescend procedure, so

Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets

11

ZDescend(F, t){ while(F.top > t)
{ G ← cache(“ZSkip at F ”) ;if (G exists and G.top ≥ t) F ← G ;else F ← (0-Child of F ) ;}return F ;}Figure 10: ZDD Traversal Using Z-Skip-Links.
SetZSkip(F ){ if (F.top ≤ 4) return ;if (cache(“ZSkip at F ”) exists) return ;SetZSkip(0-Child of F ) ;t ← (F.top − J(F.top)) ; /* Destination fromF */G ← ZDescend(F, t) ;cache(“ZSkip at F ”) ← G ;SetZSkip(1-Child of F ) ;}Figure 11: Construction of Z-Skip-Links.

we need several steps to reach the destination node. In the range of n ≤ 65536,
ZDescend procedure requires about 20 to 30 steps in average, therefore, the total
computation time will be several ten times of the number of ZDD nodes. This
would be feasible overhead if we repeat the search process many times for a largescale sparse dataset.

6

Experimental Results

We implemented the algorithms and conducted experiments for performance evaluation. The speciﬁcation of our PC is as follows. Intel Core i7 2700K 3.5GHz,
32GB memory, OpenSuSE Linux 12.1 (64bit), GNU C++ 4.6.2. We used our own
BDD/ZDD package written in C and C++.

6.1

Membership Testing for Random-Generated Sparse Datasets

We applied our method to the randomly generated large-scale sparse datasets. We
generated a ZDD for the dataset D(n,m) including m combinations each of which
randomly selecting two items out of n times. Next we also randomly generate a twoitem pattern p and evaluate the computation time for the membership testing if p
is in D(n,m) . We executed SetZSkip procedure for the ZDD as preprocessing andthen repeat the membership testing 10000 times with diﬀerent p’s. We compared
our method with conventional ZDD-based membership operation as D(n,m) ∩ p(n) .

12Shin-ichi Minato

Table 2: Results for Random-Generated Sparse Datasets.
ZDD
CPU time(sec)accel.
nm
nodes
pre- searchold
net grossprc. x10000 x10000
1,000
10,00010,011 0.004
0.012
0.158
13.2
9.9
2,000
20,00020,181 0.005
0.013
0.390
30.0 21.7
5,000
50,00050,683 0.007
0.018
1.025
56.9 41.0
10,000 100,000 101,521 0.026
0.021
2.055
97.9 43.7
20,000 200,000 203,272 0.058
0.029
4.499 155.1 51.7
50,000 500,000 508,335 0.170
0.028 14.393 514.0 72.7

θ

n

100
50
20
10
5

932
1,597
2,434
2,885
3,129

Table 3: Results for Frequent Itemset Datasets.
ZDD
CPU time(sec)accel.
mnodes
pre- search
old net grossprc. x10000 x10000
11,9282,298 0.001
0.009
0.094 10.4
9.4
70,713
6,059 0.001
0.011
0.169 15.4 14.1
63,4065
30,410 0.007
0.012
0.268 22.3 14.1
4,440,335
93,899 0.021
0.012
0.328 27.3
9.9
26,946,004 353,091 0.050
0.015
0.393 26.2
6.0

The experimental results are shown in Table 2. Here “pre-prc.” means thetime for preprocessing, “old” means conventional method. “accel.” means theratio of acceleration, “net” means ignoring preprocessing time, and “gross” means
including preprocessing time. From the result, if we ignore the preprocessing time,
the acceleration ratio reaches more than 500 times when n = 50000. Even if we
including preprocessing time, more than 70 times faster than conventional method.
The experimental results show that our method is eﬀective when implementing on
the practical BDD/ZDD package.

6.2

Membership Testing for Frequent Itemset Datasets

Next we applied our method to the frequent itemset data, which are dealt with in
the basic problem of data mining. We used a dataset “BMS-WebView2” chosenfrom the KDD benchmark [4]. This data is known as the access log of web pages
at an Internet shopping site, This dataset has 3340 items and 77512 transactions(combinations), but only 4.6 items appears in average per transaction, so it hasvery sparse combinations. We applied LCM-ZDD method[10] to this dataset andgenerate a ZDD Dθ including all frequent itemset patterns with a given minimum
support θ. For example, D5 includes 26946004 patterns and there are 3129 relevant
items. The number of ZDD nodes are only 353091, so it has very good compression
rate.
Then, we also randomly generate a two item pattern p, and similarly evaluate
the computation time for the membership testing if p is in Dθ . Table 2 show that

Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets

13

our method is 10 to 27 times faster than conventional method without considering
preprocessing time, and 6 to 14 times faster with considering preprocessing time.

7

Summary

We proposed Z-Skip-Links to accelerate the traversal of ZDDs of large-scale sparse
datasets. It consumes only a constant size of additional memory, and can easily be
implemented into a conventional BDD/ZDD package. We analyzed the averagecase computation time and have clariﬁed the optimal settings. Our experiments
show that the use of Z-Skip-Links makes the membership operations much fasterthan using conventional ZDD operations when handling large-scale sparse datasets.
We expect that our method will widen the eﬀective applications of ZDDs in theera of Big Data.

References[1] S. B. Akers. Binary decision diagrams. IEEE Transactions on Computers,
C-27(6):509–516, 1978.
[2] R. E. Bryant. Graph-based algorithms for Boolean function manipulation.
IEEE Transactions on Computers, C-35(8):677–691, 1986.
[3] Olivier Coudert. Solving graph optimization problems with ZBDDs. In Proc.
of ACM/IEEE European Design and Test Conference (ED&TC ’97), pages
224–228, 1997.
[4] B. Goethals and M. J. Zaki. Frequent itemset mining dataset repository, 2003.
Frequent Itemset Mining Implementations (FIMI’03),
http://ﬁmi.cs.helsinki.ﬁ/.
[5] M. Ishihata, Y. Kameya, T. Sato, and S. Minato. Propositionalizing the EM
algorithm by BDDs. In Proc. of 18th International Conference on Inductive
Logic Programming (ILP 2008), 9 2008.
[6] D. E. Knuth. The Art of Computer Programming: Bitwise Tricks & Techniques; Binary Decision Diagrams, volume 4, fascicle 1. Addison-Wesley,
2009.
[7] E. Loekit and J. Bailey. Fast mining of high dimensional expressive contrast
patterns using zero-suppressed binary decision diagrams. In Proc. of 12th
ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining (KDD2006), pages 307–316, 2006.
[8] S. Minato, K. Satoh, and T. Sato. Compiling bayesian networks by symbolic probability calculation based on zero-suppressed BDDs. In Proc. of 20th

14

Shin-ichi Minato

International Joint Conference of Artificial Intelligence (IJCAI-2007), pages
2550–2555, 2007.
[9] Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proc. of 30th ACM/IEEE Design Automation Conference(DAC’93), pages 272–277, 1993.
[10] Shin-ichi Minato, Takeaki Uno, and Hiroki Arimura. LCM over ZBDDs: Fast
generation of very large-scale frequent itemsets using a compact graph-based
representation. In Proc. of 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2008), (LNAI 5012, Springer), pages 234–
246, 2008.
[11] William Pugh. Skip lists: A probabilistic alternative to balanced trees. Algorithms and Data Structures, 33(6):668–676, 1990.
[12] Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura, and Shinichi Minato. Counterexamples to the long-standing conjecture on the complexity of bdd binary operations. Information Processing Letters, 112(16):636–640,
2012.

Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets

A

Calculation in Average-Case Analysis

A.1

Calculation of C(n) in Basic Model15

As the target t is assumed discrete uniform distribution from 1 to n, the probability of passing through the target by a jump becomes 1/α if x is enough large.
Therefore, C1 (n), the average number of jumps from n, can be described as follows.




1
1
1
1
1 2
+ ...
1−
+3·
1−
C1 (n) = 1 · + 2 ·
α
α
α
α
α


∞

1
1 i−1
=
i·
1−
α
α
i=1

= α

(10)

Namely, if we use the skip length function J(x) = x/α, C1 (x) becomes constantvalue α for any large number n. When α = 4, we need only 4 times of jumps inaverage to reach vicinity to the target even if n = 10000.
Next, let us consider C2 (n). Here R1 (n) denotes the average length of the last
jump, then it is written as:








1
1
1
1
1
1
1
1
1 2
1 2
R1 (n) =
n·
+ ...
n· +
1−
n·
1−
+
1−
1−
α
α α
α
α
α
α
α
α
α
 2 ∞1
1 2(i−1)
=
n
1−
α
α
i=1
n
=
(11)
2(α − 2)At the position of just before the last jump, the target t is located in the distanceof 0 to R1 (n) − 1. As we assume t has uniform distribution, we get:C2 (n) =R1 (n)n=24(α − 2)and thus,
C(n) = C1 (n) + C2 (n) = α +n4(α − 2)

(12)

is obtained.

A.2

Calculation of C(n) in Two-Phase Model

Here we assume the same skip length as 1/α of remaining search range for both
J1 (x) and J2 (x). Then we can write as:
 


1
1
(13)
x , J2 (x) =R1 (x)J1 (x) =αα16Shin-ichi Minato(R1 (n) is the average length of the last jump of J1 , and it becomes the initial
search range of J2 .)Let us consider C1 (n), C2 (n), and C3 (n) when using such J1 (x) and J2 (x). First,
J1 ’s condition is completely same as the basic model,
C1 (n) = α, R1 (n) =n2(α − 2)

as well as equation 10, 11.
Next, we consider C2 (n), however, it jumps 1/α distance as well as J1 , we also
get C2 (n) = α. R2 (n) is obtained by substituting R1 (n) into n:
R2 (n) =R1 (n)n=2(α − 2)4(α − 2)2

and thus,
C3 (n) =R2 (n)n=28(α − 2)2

Consequently, the total cost is:C(n) = C1 (n) + C2 (n) + C3 (n) = 2α +n8(α − 2)2

(14)

Let us calculate optimal α for a given n in a similar way as the basic model.
The derivative of C(n) with respect to α is written as:dnC(n) = 2 −dα4(α − 2)3
and it must be zero, then:3n3
αopt =+ 2, Copt (n) = 3 n + 4
2
2

(15)

are obtained.

A.3

(k

)

Calculation of Coptopt (n) in k-Phase Model

The average cost in k-phase model is written as:
C (k) (n) = kα +n2k+1 (α − 2)k(16)

For calculating optimal α, the derivative of C (k) (n) with respect to α can be written
as:
d (k)
kn
C (n) = k − k+1dα
2 (α − 2)k+1

Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets

17

and it should be zero, then:
1 1
αopt = n k+1 + 2,2(k)Copt (n) =1
k + 1 k+1
+ 2k
n
2

(17)

are obtained.
1= t, then we canNext, let us consider the optimal k for given n. If we set k+1(k)rewrite Copt (n) as:(k)

Copt (n) =nt + 4− 2.
2tThen calculate the derivative by t,(t ln n − 1)ntd (k)Copt (n) =dtt2
and it becomes zero when t = ln1n , thus,(k)

kopt = ln n − 1, Coptopt (n) =are obtained.

5
ln n − 22(18)