ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造

摘要

多くの実問題の中において，集合族を扱う必要に迫られることはままあることである.大規模な集合族を操作することはウェブからの情報抽出や，情報統合，データマイニングに対する重要な基盤技術である.こういった目的に対し，ゼロサプレス型二分決定グラフ（ZDD)と呼ばれる特別な二分決定グラフ（BDD)が使用されることがある.しかしながらZDDを格納するためには巨大なメモリ領域が必要であり，また所属性判定演算も低速であるという問題がある.本論文では静的なZDDを圧縮した索引である密集ゼロサプレス型二分決定グラフ（Dense ZDD)を導入する.この技術では集合族をコンパクトに索引化するだけではなく所属性判定演算も高速に行えるようになる.さらに，DenseZDDと通常のZDDの混成手法により動的な索引を実現する方法も提案する.%In many real-life problems, we are often faced with manipulating families of sets. Manipulation of large-scale set families is one of the important fundamental techniques for web information retrieval, integration, and mining. For this purpose, a special type of binary decision diagram (BDD), called Zero-suppressed BDDs (ZDDs), is used. However there is a problem of huge required space for storing ZDDs and slow membership opera­tions. This paper introduces DenseZDD, a compressed index for static ZDDs. Our technique not only indexes set families compactly but also executes fast membership operations. We also propose a hybrid method of DenseZDD and ordinary ZDDs to make the index dynamic.