Compact and Fast Indices Based on Zero-Suppressed Binary Decision Diagrams (コンピュテーション) Compact and Fast Indices Based on Zero-Suppressed Binary Decision Diagrams

この論文をさがす

著者

    • 津田 宏治 [他] TSUDA Koji
    • 産業技術総合研究所生命情報工学研究センター:JST ERATO湊離散構造処理系プロジェクト AIST Computational Biology Research Center:JST ERATO Minato Discrete Structure Manipulation System Project
    • 湊 真一 MINATO Shin-ichi
    • 北海道大学情報科学研究科:JST ERATO湊離散構造処理系プロジェクト Graduate School of Information Science and Technology, Hokkaido University:JST ERATO Minato Discrete Structure Manipulation System Project

抄録

多くの実問題の中において,集合族を扱う必要に迫られることはままあることである.大規模な集合族を操作することはウェブからの情報抽出や,情報統合,データマイニングに対する重要な基盤技術である.こういった目的に対し,ゼロサプレス型二分決定グラフ(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)js 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.

収録刊行物

  • 電子情報通信学会技術研究報告 : 信学技報

    電子情報通信学会技術研究報告 : 信学技報 112(498), 23-30, 2013-03-18

    一般社団法人電子情報通信学会

各種コード

  • NII論文ID(NAID)
    110009713173
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    ENG
  • ISSN
    0913-5685
  • NDL 記事登録ID
    024409638
  • NDL 請求記号
    Z16-940
  • データ提供元
    NDL  NII-ELS 
ページトップへ