系列を表す二分決定グラフを用いた大規模データベースの解析処理アルゴリズムの研究

使用表示序列的二元决策图的大规模数据库分析处理算法研究

• 批准号: 13J01937
• 负责人: 伝住 周平
• 金额: $ 1.15万
• 依托单位: Hokkaido University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2013
• 资助国家: 日本
• 起止时间: 2013-04-01 至 2015-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13J01937/
• 关键词: 系列二分決定グラフ; 二分決定グラフ; 非循環決定性オートマトン; 簡潔データ構造; 圧縮処理; アルゴリズム; データ構造; 離散構造; 知識発見とデータマイニング; アルゴリズム理論; 情報検索

系列二分決定グラフ（ＳｅｑＢＤＤ）は２００９年に提案されたデータ構造である．ＳｅｑＢＤＤは従来の非循環決定性有限オートマトン（ＡＤＦＡ）に二分決定グラフ（ＢＤＤ）の技術を導入したもので，系列の集合を効率良く表現・操作することができる．ＢＤＤとはグラフを用いたブール関数データの表現方法であり，ＶＬＳＩ設計自動化の分野で発展してきた技術である．その特徴は，実メモリ上に大規模な単一のハッシュ表を用意し，冗長な部分グラフの生成を一切排除する技法である．ＳｅｑＢＤＤはＢＤＤから継承した多様なアルゴリズムを保持しており，系列集合に対して効率良く演算を実行することができる．情報検索において扱うデータが巨大になると，索引構造の構築時間やサイズ，検索速度が問題となる．ＳｅｑＢＤＤを用いる場合，構築時間と検索速度に関しては問題ないが，データ構造を実メモリ上に展開するため，他の索引に比べ非常に多くの主記憶領域を必要とする．また，ＳｅｑＢＤＤはその基本的な性質もわかっていなかった．今年度は，二分決定グラフの構造情報を木構造・整数列・ビット列に変換した後に圧縮して格納することで，コンパクトかつ高速検索可能なデータ構造を生成するアルゴリズムの基盤を構築した．さらに簡潔データ構造の技法を用いて，メンバシップ演算を高速に実行するための冗長性を追加する方法の検討を進め，記憶効率と計算速度のトレードオフの見極めを行った．加えて，従来のＳｅｑＢＤＤの技術を組合わせ，高速性・簡潔性と動的な更新を両立させるハイブリッド手法を考案した．また，ＳｅｑＢＤＤの最小性や，基礎的な演算の計算量，ＡＤＦＡと比べてコンパクトであることなどを明らかにした．本研究成果は，国際会議ＳＥＡ２０１４と論文誌ＤＡＭで発表された．簡潔データ構造の分野で著名な研究者と活発に意見交換し，さらなる発展への道筋を得ることができた．

SeqBDD is a 2009 proposal to introduce techniques for non-cyclic deterministic finite element analysis (ADFA) and binary decision generation (BDD). The characteristics of the system are: 1) the size of the system; 2) the length of the system; 3) the size of the system; 4) the size of the system; and 5) the size of the system. Information search is very important, index construction time and search speed are important, index construction time and search speed are important, index construction time and search speed are important, index construction time and search speed are important. SeqBDD is the basic property of SeqBDD. This year, the structure information of the two-part decision tree structure, integer column, column, conversion, compression, and so on, the high-speed search possible structure, generation, and construction of the substrate. In this paper, the technique of concise structure is used to improve the memory efficiency and calculation speed of high speed calculation, and the method of adding redundancy is discussed. The technology of SeqBDD is combined with high speed, simplicity and dynamic updating. SeqBDD is the minimum property of the calculation, ADFA is the minimum property of the calculation, ADFA is the minimum property of the calculation. The results of this research are presented in the DAM paper of SEA2014. A brief introduction to the structure of the division between the famous researchers and the active exchange of views, today's development of the road tendon to get the right time.

项目成果

Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations

• DOI: 10.1016/j.dam.2014.11.022
• 发表时间: 2016-10
• 期刊: Discret. Appl. Math.
• 作者: Shuhei Denzumi;Ryo Yoshinaka;Hiroki Arimura;S. Minato

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagrams

• 发表时间: 2013
• 作者: Shuhei Denzumi;K. Tsuda;Hiroki Arimura;S. Minato

Manipulation of Sets of Strings Using Sequence Binary Decision Diagrams

使用序列二元决策图操作字符串集

• 发表时间: 2015
• 作者: R. Lozeva;A. Odahara;C.-B. Moon;S. Nishimura;P. Doornenbal;H. Naidja;F. Nowacki;P.-A. Soderstrom;T. Sumikama;G. Lorusso;J. Wu;Z.Y. Xu;et al.;Yoshitaka Kawasoe;Shuhei Denzumi
• 通讯作者: Shuhei Denzumi

"DenseZDD: A Compact and Fast Index for Families of Sets"

“DenseZDD：针对集合族的紧凑且快速的索引”

• DOI: 10.3390/a11080128
• 发表时间: 2018
• 期刊: Algorithms
• 影响因子: 2.3
• 作者: Shuhei Denzumi;Jun Kawahara;Koji Tsuda;Hiroki Arimura;Shin-ichi Minato;and Kunihiko Sadakane
• 通讯作者: and Kunihiko Sadakane