NTTは、2024年6月25日、グラフ探索を高速化するアルゴリズムを開発したことを発表した。 多くの情報は事物のネットワーク構造として解釈可能であり、そのつながりを「頂点」と「辺」で表現するグラフは、都市インフラやAI、セキュリティ、創薬などの分野で重要視されている。 このグラフデータの活用に向け、同社ではグラフ処理における基礎的な要素技術であるBFS(幅優先探索)の研究を続けてきた。BFSは、グラフ全体の頂点を近い順に辿る計算方法となる。 木構造の事前分離により BFS木構築を高速化 今回NTTが確立したのは、「Forest Pruning」という、始点から近い順に頂点を辿るための「BFS木」の構築を高速化するアルゴリズムだ。 まず、事前計算でグラフの一部(木構造部分)を分離。始点が与えられた際に、残ったグラフで頂点を辿って部分的なBFS木を構築する。そこに分離しておいた木構造部分を接合
![NTTがグラフ探索の高速化アルゴリズム開発 スパコン富岳のBFS世界1位に貢献](https://cdn-ak-scissors.b.st-hatena.com/image/square/371f1808c1248e31c76e0982db90d201056d1656/height=288;version=1;width=512/https%3A%2F%2Fascii.jp%2Fimg%2F2024%2F06%2F25%2F3754075%2Fxl%2Fc96a497041f91d7f.jpg%3F20200122)