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

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

基本信息

批准号：
13J01937
负责人：
伝住周平
金额：
$ 1.15万
依托单位：
Hokkaido University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2013
资助国家：
日本
起止时间：
2013-04-01 至 2015-03-31
项目状态：
已结题

项目摘要

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

顺序二元决策图（SeqBDD）是2009年提出的一种数据结构。 SeqBDD将二元决策图（BDD）技术引入到传统的非循环确定性有限自动机（ADFA）中，可以有效地表示和操作序列集。 BDD是一种使用图形表达布尔函数数据的方法，是在VLSI设计自动化领域发展起来的技术。其特点是在实内存中准备单个大规模哈希表并消除冗余子图的生成的技术。 SeqBDD维护了从BDD继承的各种算法，可以高效地对序列集进行操作。当信息检索处理的数据量变得巨大时，索引结构构建的时间和规模以及搜索速度就成为问题。使用SeqBDD时，在构建时间和搜索速度方面没有问题，但由于数据结构是在实内存上开发的，因此它需要比其他索引明显更大的主存储空间。此外，SeqBDD 的基本属性尚不清楚。今年，我们通过将二元决策图的结构信息转换为树结构、整数序列和位序列，压缩并存储它们，为生成紧凑且高速可搜索数据结构的算法奠定了基础。此外，利用简洁的数据结构技术，我们研究了一种添加冗余以高速执行成员资格操作的方法，并确定了存储效率和计算速度之间的权衡。此外，通过结合传统的SeqBDD技术，我们设计了一种混合方法，可以实现高速、简单和动态更新。我们还展示了 SeqBDD 的极简性、所需的基本计算量以及与 ADFA 相比的紧凑性。这项研究的结果发表在国际会议 SEA2014 和 DAM 杂志上。我们与简洁数据结构领域的知名研究人员进行了热烈的交流，并获得了进一步的发展之路。