ディスク上の大規模グラフデータを対象とした集合単位ナビゲーションの効率化∗
只石正輝 (学籍番号 200821664)
研究指導教員: 森嶋厚行
副研究指導教員: 鈴木伸崇

1. はじめに1i"" bb"
b 10i
2i6i

今日，計算機で扱われているデータを表現する形
式として，ノード (頂点) とノード間をつなぐ矢印で Tあるエッジ (辺) で構成されたグラフ構造が広く利

 T



i12i
3i4i5i7i8i9i11用されている．たとえば，計算機のディレクトリ構
造はグラフ構造の一種である木構造で表現されていsequential read of disk blocks

る．また，SNS の一つである twitter [1] では各ユー

i11 121 2i3 4 5 6i7 8 9 10-

ザをノードとし，ユーザ u1 がユーザ u2 を follow
図1している (u1 が u2 の発言を取得している) という深さ優先順での a → X

ユーザ間のつながり (u1 → u2 ) をエッジとした印の向きとは逆の向きに，1 回，または 0 回以上たグラフ構造で表現されている．また，これらのデーどることで得られるノード集合を計算する演算であf ollow

タのサイズは非常に巨大である．

∗る．残りの 4 つの演算は，a → X ， a → X ， X → a，∗

したがって，大規模なグラフ構造に対する問合せの効率化は重要な問題である．たとえば，次のような問合せを効率的に処理することは重要である．

Q1:コンピュータのディレクトリ構造において，あるディレクトリ d 以下に存在する全てのファイルの集合を計算する問合せ．Q2:人間関係等を表した
SNS データにおいて，あるユーザ u が follow してX → a の演算をラベル l を持つエッジのみに限定して行う演算である．

Q1 や Q2 は，これらの演算を利用することで∗記述可能である．たとえば Q1 は d → X ，Q2 はf ollow

u → X と記述可能である．

2. ディスク上の大規模グラフデータを対象とした集合単位ナビゲーションの効率化いる人物の集合を取得する問合せ．
しかし，これらの問合せの処理の効率化は難しい．
なぜなら，大規模グラフデータはディスクに格納して演算を処理する必要があるが，ディスク上のグラフデータに対する問合せ処理の効率的なアルゴリズ

序で各ノードをディスクに配置することで，問合せ処理の効率化を行う．その基本となるアイデアは，問合せの解となるノードができるだけ連続して配置ムは知られていないためである．
そこで本研究では，計算機のディスク上に格納された大規模グラフデータを効率よく処理するための手法を開発した．具体的には，Q1 や Q2 などの問合せを記述可能な演算である次の 8 つの集合単位ナビゲーションの効率化を目的として研究を行った．
∗提案手法では，集合単位ナビゲーションの処理をするために必要な I/O コストが小さくなるような順∗a → X, a → X, X → a, X → a,ll∗
ll∗
a → X, a → X, X → a, X → a.
ここで， a → X は，あるノード a からエッジを矢印の向きに従って，1 回たどることで得られるノー∗ド集合を計算する演算である．また，a → X は，あるノード a からエッジを矢印の向きに従って，0 回以上たどることで得られるノード集合を計算する演∗算である．X → a，X → a はそれぞれ，エッジを矢されるような順序でノードをディスクに配置することである．この配置順序によって，アクセスする必要があるディスクページの数が少なくなり，効率的に問合せを処理することが可能となる．
ノードの配置順序としては，一般には深さ優先順や幅優先順が考えられる．しかし単純な深さ優先順では a → X の解が，また単純な幅優先順では∗a → X の解が連続して配置されない．その例を図 1を用いて説明する．図 1(下) は，図 1(上) の木の各ノードを深さ優先順に配置したものである．このとき，a → X の解は連続して配置されるとは限らない．たとえば，図 1(下) において 1 → X の解となるノード集合 ({2,6,10}) は連続して配置されていな∗

い．また，木を幅優先順で配置した場合，a → X は連続して配置されない．

∗ “Eﬃcient

Processing of Set-Based Navigations for Large Graph Data on the Disk” by
Masateru TADAISHI

本研究で提案するノードの配置順序を図 2 に示す．図 2 において，各ノードに振られた番号が各ノードの配置順序を表す．提案するノード配置順序

1000000を配置する．

staircase join
oursl

提 案 し た ノ ー ド 配 置 順 序 で は X → a，X → a，elapsed time(ms)100000∗l∗

X → a， X → a の解は連続して配置されない．そ10000のため，問合せを効率的に処理できない可能性があ1000る．この問題に対して，木のルートのように多くの
100

図 2

問合せの解に含まれるノードをキャッシュとしてメ提案

10Q1Q2Q3するノード
配置順序
lQ4Q5queries

図3Q6Q7Q83. 評価実験

実験結果
∗l∗

モリ上に保持することで I/O コストを小さくする．

では，a → X ，a → X ，a → X ，a → X の問合せはlいずれも効率的に処理可能となる．まず，a → X ，l∗提案手法を評価するために実験を行った．実験
環境は次のとおりである．OS Windows XP SP2，a → X の両方の解が連続して配置される．たとえtt∗
ば，1 → X や，1 → X はいずれも連続して配置されている．次に，a → X でアクセスする必要がある連続したディスク領域の数は，a を始点とするエッジのラベルの数となる．たとえば，3 → X の解は，2つの連続したディスク領域 ({5}，{8}) にアクセス∗することで解を取得可能である．また，a → X の処置し問合せを処理する手法である Staircase join [2]

理でアクセスする必要がある連続したディスク領域

実験内容. 実験で用いた木は，著者が所属する研究の数は 2 つとなる．たとえば，2 → X の解は，2 つ室のファイルサーバである．ファイルサーバに存在の領域 ({4}，{6, 7} が存在する領域) にアクセスすするファイル／ディレクトリの総数は 8,024,321 でることで解を取得可能である．

ある．この木のエッジラベルは，ディレクトリから∗提案するノードの配置順序は次の 2 つの Step で決定する．Step 1 ノードをクラスタリングし，各CPU Pentium M 1.73 GHz，メモリ 512MB．またプログラムの実装言語は Java である．
実験では，提案手法と深さ優先順で各ノードを配との比較を行った．通常の Staircase join ではキャッシュを考慮していないため，提案手法でも同様にキャッシュを利用せずに問合せを処理した．

ディレクトリへのエッジの場合 subdir，それ以外の場合 contains となる．

クラスタを深さ優先順に配置．Step 2 クラスタ内実験では，次の 8 つの集合単位ナビゲーションをのノード配置を決定．以降ではそれぞれについて順処理し，実行時間を測定した．(Q1: d → X, Q2:subdirsubdir∗

subdirsubdir∗

ルートを一つのクラスタとする．2. ルートから同一

d → X, Q3: X → d, Q4: X → d, Q5:∗∗
a → X, Q6: a → X, Q7: X → a, Q8: X → a) ここで，d，a は，それぞれディレクトリ，ノード (ディレクトリかファイルのいずれか) を表している．
実験結果. 図 3 に実験結果を示す．図 3 において，実行時間はそれぞれのナビゲーションを 100 回行っのエッジラベルで到達可能なノード集合を一つのクた結果の合計である．実験から，問合せ処理の実行ラスタとする．3. 別のエッジラベルが出現したと時間は，Staircase join とほぼ同じ (Q3，Q4，Q6，

き 2. で得られたクラスタの各ノードをルートとし，Q7) か，Staircase join よりも効率的に問合せを処理可能である (Q1，Q2，Q5，Q8) ことが分かった．に説明する．

Step 1 ノードのクラスタリング．図 2 を用いてノードのクラスタリングについて説明する．図 2 において矩形が一つのクラスタに対応する．クラスタリングは次の 3 つを順に適用することで行う．1.

2. を適用する．たとえば図 2 において，ルートノードを一つのクラスタとし，ルートノードから同一のエッジラベル t で到達可能なノード集合 {2, 3, 4, 5}

4. まとめを一つのクラスタとする．最後に，異なるエッジラ

本研究では，大規模グラフに対する集合単位ナビベル w が出現したとき，クラスタの各ノード (3，4)

ゲーションを効率化するためのディスク格納手法をそれぞれルートとし，再帰的にクラスタリングをを提案した．問合せを効率的に処理するために，問行う．その後，各クラスタを深さ優先順に配置する．

合せの解となるノードが連続して配置されるように

Step 2 ノードの配置順序の決定．各ノードの順序は次のように決定する．1. 兄弟ノードごとにグルーピング．2. 各兄弟グループを深さ優先順に配置．た
とえば図 2 での {2, 3, 4, 5} の順序を決定する場合，兄弟ノードごとに {2, 3}，{4}，{5} の 3 つのグルーディスク上に各ノードを配置した．実験では，提案プにグルーピング後，各兄弟グループを深さ優先順に配置するため，{2, 3}，{4}，{5} の順に各ノード手法が既存の手法よりも優れていることを示した．

文献[1] http://twitter.com[2] Torsten Grust, Maurice van Keulen, and Jens Teubner. Staircase join: Teach a relational DBMS towatch its (axis) steps. In VLDB, pp. 524–525, 2003.