1.1 Summary

ZDD (Zero-suppressed Binary Decision Diagrams) is a data structure used for efficient manipulation of weighted item combinations based on reduction rules. ZDD VSOP (Valued-Sum-of-Products calculator)[ is implemented as a Ruby Extension Library for the computation of item combinations.

The founder of ZDD, Professor Shin-ichi Minato, developed a ZDD program which is made available for extended development in Ruby language. The Ruby Extension Library for ZDD is therefore developed in collaboration with ERATO Minato Discrete Structure Manipulation System Project.

ZDD can enumerate huge number of combinations represented in a compact structure. For example, to enumerate all possible combinations of the products (frequent itemsets) purchased from the supermarket in the purchase history at a defined minimum support, in most cases, the number of combinations generated will grow exponentially. The ZDD data structure therefore is designed to provide a powerful framework to store all possible combinations in an unique and compact form efficiently.

Various calculations can be applied directly on ZDD objects where large scale itemsets are stored in a compact form for efficient processing. For example, users will be able to select the patterns containing "natto" from millions of enumerated frequent itemsets, or identify the differences of frequent itemset patterns between male and female. It is also possible to compute the ratio of size of ZDD. For details on theoretical context, please refer to the reference at the end of this document.

In this package, ZDD is handled as (known as ZDD object) Ruby object. Various functions for the ZDD objects correspond to class methods, operator overloading is used for ZDD objects using operands for ZDD object (+,-,== etc.), to enable seamlessly integration of functions between Ruby and ZDD.

The ZDD package also supports automatic type conversion designed to reduce stress on programming.