グラフ解析の性能

グラフ解析における非常に重要な処理として最短路計算があります。具体的にはグラフ上で始点と終点を指定して、この二点間の最短路を計算するのが目的です。最短路計算の性能を表す指標としては実行時間の他にも１秒間に何本の枝を通過できるかを測定するTEPS(Traversed Edges Per Second) 値があります。現在のCPU 1 コアで10^7 = 1000 万TEPS 以上の性能を出すことができますので、全米データ(2400万点, 5800 万枝：下図) に対する最短路計算は 5 秒程度で終了することができます(最短路計算においては全ての枝を 1 回程度通過するため）。また複数の CPU コアで並列計算を行う場合ではさらに大きなTEPS値を出すことが加能です。