講演抄録/キーワード |
講演名 |
2013-03-18 13:45
ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造 ○伝住周平(北大)・川原 純(奈良先端大)・津田宏治(産総研/JST)・有村博紀(北大)・湊 真一(北大/JST)・定兼邦彦(NII) COMP2012-56 |
抄録 |
(和) |
多くの実問題の中において,集合族を扱う必要に迫られることはままあることである.大規模な集合族を操作することはウェブからの情報抽出や,情報統合,データマイニングに対する重要な基盤技術である.こういった目的に対し,ゼロサプレス型二分決定グラフ(ZDD)と呼ばれる特別な二分決定グラフ(BDD)が使用されることがある.しかしながらZDDを格納するためには巨大なメモリ領域が必要であり,また所属性判定演算も低速であるという問題がある.本論文では静的なZDDを圧縮した索引である集辺式ゼロサプレス型二分決定グラフ(DenseZDD)を導入する.この技術では集合族をコンパクトに索引化するだけではなく所属性判定演算も高速に行えるようになる.さらに,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 operations. 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. |
キーワード |
(和) |
二分決定グラフ / BDD / ゼロサプレス型二分決定グラフ / ZDD / 簡潔データ構造 / 集合族 / 所属性判定演算 / 集辺式ゼロサプレス型二分決定グラフ |
(英) |
binary decision diagram / BDD / zero-suppressed binary decision diagram / ZDD / succinct data structure / family of sets / membership operation / DenseZDD |
文献情報 |
信学技報, vol. 112, no. 498, COMP2012-56, pp. 23-30, 2013年3月. |
資料番号 |
COMP2012-56 |
発行日 |
2013-03-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-56 |