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

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

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