1.4 Terminologies

The following section explains the terminologies used in this manual. Note that there may be differences of the terms used in the reference at the end of this manual.

Item, Itemset, Term, Valued sum of products set, Expression

An element in a set is referred to as "item", and an "itemset" contains a group of item elements.

The concept is easier to understand when these terms are set into context in a supermarket scenario. Commodity products are considered as items, and the combination of the products are referred to as itemset. When weight is attached to a "term" in the itemset, it is known as "valued sum of products set". For example, the valued sum of products for 3 items a,b,c is represented as "abc+3ab+4bc+7c" (this notation is referred to as "valued sum of products format"). It consists of four terms abc,3ab,4bc,7c. In this case, 3ab consists of weight of 3 for itemset {a,b}. Back to the supermarket scenario, this means that one customer purchased 3 products a,b,c at the same time, and there are three customers who bought a,b at the same time.

Empty itemset, ZDD constant object

The itemset without element is referred to as "empty itemset". Considering the valued sum of products set "abc+3ab+4bc+7c+3", the a weight of 3 is attached to an empty itemset and thus it is shown as 3.

In supermarket scenario, it means that there are three customers did not purchase anything. Thus, empty itemsets of ZDD object is referred to as ZDD constant object.

Item order table

ZDD is a binary decision tree that contains a compact decision tree graph, and the level of the decision tree (depth) corresponds to the item. Further, this level, the order from root to the leaves is managed by the table known as "item order table".

It is important to manage item order since the order significantly impacts the size of ZDD (number of nodes). When the size of the ZDD increases, the processing speed will be reduced accordingly. The item order table can be registered at any time using the symbol function. If the number of combinations is extremely large, it is necessary to use the order table to register order of items.