データベースの頻出アイテム集合を表すゼロサプレス型BDDの変数順序付けの理論的考察

摘要

ゼロサプレス型BDD（Zer（ト凱Ippl?e鋸edBinaryDecisioIIDiと1gI，乱町ZBDI〕）を仙、て，データベースの頻出アイテム集合を高速に抽出しコンパクトに表現する新しい手法が提案されている．w－?般にZ王?DDは変数の順序付けによりそのサイズが著しく変化することが知られているが，頻用アイテム集合を表現する場合の順序付けの影奄削まあまり深く研究されていなかった．本稿では，変数順序付けによりZBDDのサイズが指数関数的に変化する人工的な例題を作成できることを示し，2つの典型的な例月副こついて，指数関数的な影響が生じる理由を理論的に考察する．Recently, an efficient method has been proposed to use Zero-suppressed Binary Decision Diagrams (ZBDDs) for extracting and representing a huge amount of frequent itemsets in data mining. In general, it is well-known that the size of ZBDDs greatly depend on variable ordering, however, in the specific cases of applying ZBDDs to data mining, the effect of variable ordering has not been understood well. In. this paper, we show two typical database examples we found out, where the ZBDD size is exponentially sensitive to variable ordering. We discuss why they are so sensitive.