情報処理学会 第78回全国大会講演要旨

大規模なグラフにおける到達可能性クエリ問題に対して，頂点へのレベル（順位）付けを行い，そのレベルに沿ってラベルを構築し，構築したラベルを用いることにより，各到達可能性クエリに対して高速に回答するという手法がある．この手法は頂点へのレベルの付け方に依存しており，ラベルの構築に掛かる時間やラベルのサイズ等に多大な影響を与える．そこで，ラベル構築時間，レベル付け時間，ラベルサイズ，クエリの平均応答時間の観点から，いくつかのレベル付け方法により性能を比較し，どのレベル付け方法が有用かを検証した．