HOME / 研究展示 / ネットワーク構造に関する様々な質問に答えます
研究展示
データと学習の科学
03

ネットワーク構造に関する様々な質問に答えます

ゼロサプレス型項分岐決定グラフを用いたグラフ構造索引

ネットワーク構造に関する様々な質問に答えます
どんな研究

ネットワーク構造に関する情報を小さく表現する部分構造索引を用いて、効率的に特定の構造を発見したり、数を数えたりする方法を研究しています。 部分構造索引を用いると、通信網や道路網などの、ネットワーク構造をもつ多様な問題を効率的に解くことができます。

どこが凄い

新しい部分構造索引であるゼロサプレス型項分岐決定グラフ(ZSDD)、およびZSDDを効率的に構築するアルゴリズムを考案しました。考案した技術を用いるとこれまでよりも小さな索引を構築できます。索引を小さくしたぶんだけ多様な問題をより高速に解決できます。

めざす未来

アルゴリズムの改良は、計算機の性能向上だけでは容易に達成できない、計算の劇的な高速化をもたらします。考案したアルゴリズムを利用しやすい形で整備することにより、応用問題でより良い解を発見できるようになるなど、効率的な社会の実現に貢献します。

ネットワーク構造に関する様々な質問に答えます
関連文献

[1] M. Nishino, N. Yasuda, S. Minato, M. Nagata, “Zero-suppressed Sentential Decision Diagrams,” in Proc. 30th AAAI Conference on Artificial Intelligence (AAAI 16), 2016.
[2] M. Nishino, N. Yasuda, S. Minato, M. Nagata, “Compiling Graph Substructures into Sentential Decision Diagrams,” in Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 17), 2017.
[3] Y. Nakahata, M. Nishino, J. Kawahara, S. Minato, “Enumerating All Subgraphs Under Given Constraints using Zero-suppressed Sentential Decision Diagrams,” in Proc. 18th Symposium on Experimental Algorithms (SEA 2020), 2020.

展示説明ムービー
Q&A
Q.質問/コメント A.回答
Q.質問/コメント

どうしてZSDDって名前なの?

A.回答

もともと決定グラフ(Decision Diagram,DD)とよばれる索引構造があり、ZSDDはそれにいくつかの拡張を施したものだからです。ゼロサプレス、項分岐のそれぞれがより小さな決定グラフを得るための工夫に対応します。

Q.質問/コメント

どれくらいの大きさのネットワークを扱うことができるのですか?

A.回答

ネットワークの形状にも依存しますが、数百ノード規模のネットワークを扱うことが可能です。

ポスター
連絡先

西野 正彬 (Masaaki Nishino) 協創情報研究部 言語知能研究グループ
Email: cs-openhouse-ml@hco.ntt.co.jp

他の研究展示はこちら