Incremental GIM-V 必要メモリ概算

頂点id の型を Long (int64_t) とする。
頂点id を0以上の整数として扱うならば、扱うことのできる頂点数の上限は
2^64 ≒ 9.22 エクサ個となる。
SPADEの整数型に Unsigned なものってないんですかね。

===

SPADEのリファレンスをよく見てみると、"each list is limited to 2^32 - 1 entries"
とある。RWRとHADIでは頂点の値の型およびcombine2の値の型にリストを使うので、
頂点数の上限は 2^32 - 1 ≒ 4.29 ギガ個となる。

===

各アルゴリズムで必要とするメモリの大きさを概算してみる。
頂点数を N 辺数を E と置く。

PageRankの場合、

辺の値の型は Double (8 Bytes)、これに始点id (Long ;8 Bytes) 終点id (Long)
を足すので一辺あたり 24 Bytes。辺全体で 24*E Bytes。
頂点の値の型は Double。頂点全体で 8*N Bytes。
combine2の最終値を保存しておく必要がある。
combine2の値の型は Double、これに辺の終点id(Long)を足して、辺全体で 16*E Bytes。
各頂点のグラフ分割(Byte)も保存する。頂点全体で N Bytes。
あとは頂点数や辺数に依存しないデータのみなので省略。

合計すると 32*E + 9*N Bytes

頂点数が 1Mi 辺数が 100Mi とすると全体で 3209 MiB。

===

RWRの場合、

辺の値の型 : Double
辺全体 : 24*E Bytes
頂点の値の型 : DoubleList (要素数N)
頂点全体 : 24*N*N Bytes
combine2の値の型 : DoubleList (要素数N)
combine2最終値全体 : (8*N + 8)*E Bytes
グラフ分割情報全体 : N Bytes

合計 : 8*N*E + 24*N*N + 32*E + N Bytes

頂点数が 1Mi 辺数が 100Mi とすると全体で 824 TiB (+ 3201 MiB)。大きすぎ。

===

TODO:HADI, HCCについて書く。
HADIはByteListの履歴が必要となる。非常に大きくなると思う。