"K^2-trees for Compact Web Graph Representation"という簡潔グラフの論文を読んでみた
ちょっと気になったので"K^2-trees for Compact Web Graph Representation"という簡潔グラフの論文を読んでみたよ。
K^2-trees for Compact Web Graph Representation
Nieves R. Brisaboa, Susana Ladra, Gonzalo Navarro; 2009
この論文はグラフの簡潔データ構造について書いてある。グラフというとわかりにくいかもしれない。簡単に言うとアイテム間のつながりを表現することができるのがグラフ構造。例えばHITSやPageRankではwebページのリンク関係をグラフで表現している。
具体的にはグラフは隣接行列(adjacency matrix)の形式で表現される。例えばID0, 1, 2, 3の4つのwebページがあって
0 => 1 1 => 0 2 => 0 3 => 0
というリンク関係があったとする。このときa=>bのようにaからbにリンクがあるなら、a行b列の値を1にする。すると以下の行列ができる。
0, 1, 0, 0 1, 0, 0, 0 1, 0, 0, 0 1, 0, 0, 0
これが隣接行列。これに対して冪乗法(power method)などを用いて固有ベクトルを取り出すことで、あるアイテムと関連の強いアイテムを取り出すことができる。
が、今回の本題はそこではないので置いておく。
まずは落ち着いて↑の隣接行列を見てみる。ほとんどが0になっている。一般にひとつのアイテムはそれほど多くのアイテムと関連があるわけではないので、グラフを表現する隣接行列は要素がほとんど0になる。このようなスカスカな行列を疎行列(sparse matrix)と呼ぶ。
疎行列はほとんどの要素に値が入っていない(=0)という特徴を利用すれば、データサイズを小さくすることができる。グラフでリンク構造を解析する場合は大抵データが非常に大きくなるのでデータサイズはできるだけ小さくしたい。
疎行列を小さいデータサイズでもたせる場合、一般的にはCRS(Compressed Row Storage)という方法を用いる。これは簡単に言うと要素が入っている部分だけを配列で持たせて、要素アクセスには二分探索を使おう、というもの。
さて。ここからがようやく本題。今回読んだ論文では疎行列をCRSではなく簡潔データ構造で表現しちゃうぞ！ということが書いてあった。
具体的にはグラフを木構造に変形することで不要な0の並びを持たなくて済むようにして、さらに木構造をLOUDSに似た形式で持たせることでデータサイズを小さくするよ、というのが本手法の概要。
まず、疎行列を適当な個数のブロックに分割する。例えば先ほどの行列
0, 1, 0, 0 1, 0, 0, 0 1, 0, 0, 0 1, 0, 0, 0
を4つに分割すると
(a) 0, 1 1, 0 (b) 0, 0 0, 0 (c) 1, 0 1, 0 (d) 0, 0 0, 0
となる。この4つのブロックが最初の子ノードとなる。ブロック内に1があれば子ノードの値は1に、1がなければ子ノードの値は0とする。つまり
root => { a:1, b:0, c:1, d:0 }となる。そして子ノードの値が1のノードについては再帰的にブロックを作る。今回の例ではa, cの2つのブロックが値が1なので再帰的に4つのブロックに分割する。するとブロック内にデータが1つだけになるのでここで処理が終わる。
root => { a:1, b:0, c:1, d:0 }
a => { aa:0, ab:1, ac:1, ad:0 }
c => { ca:1, cb:0, cc:1, cd:0 }このようにデータを持たせることで要素がひとつもないブロックは、子ノードを持たなくて済むためデータサイズが小さくなる。
さてここでグラフが木に変換できた。この木はLOUDSのように幅優先探索の順番でノードを並べる。つまり先頭にダミーノード(1)をくっつけて
1 1010 0110 1010
というビット列でデータを持たせる。LOUDSでは直前のノードまでの子ノード数の累計値を使うことで子ノードの位置を知ることができた。
参考:
DSIRNLP#1で発表しました「TRIEにトライ！〜今日からはじめるTRIE入門〜」 - EchizenBlog-Zwei
今回のデータではノードの値が0なら子ノード数は0、ノードの値が1なら子ノード数は4となっている(常に4つのブロックに分割していたことを思い出す)。したがってi番目のノードの子ノードの位置を知るにはrank(i) * 4 + 1とすれば良い(rank(i)でiより前にある値が1のノードの数を調べて、それらはすべて子ノード数が4なので4倍している。1は最初のダミーノード分)。
例えばノードcの子ノードの位置を調べてみる。ノードcは3番目のノードなので(先頭のダミーノードを0番目としてカウント)
rank(3) * 4 + 1 = 2 * 4 + 1 = 9
となり9番目のノードがノードcの子ノードの先頭位置であることがわかる。
以上が本論文が提案する簡潔グラフの概要。ブロックの数を調整することでデータサイズとアクセス時間を調整できる利点がある。木でデータを持っているのでO(logN)のアクセス時間がかかると思うので、(ブロック数にも拠るだろうけど)アクセス時間ではCRSと大差ないと思う。データサイズでは各要素のインデックスを持たないといけないCRSに比べるとある程度有利な気がする(論文の後半、力尽きて空間計算量の話ちゃんと読んでないです。すみません)。
