C11: 大量データ処理のための領域効率の良いアルゴリズム 定兼 邦彦 小野 廣隆 山下 雅史 (九大) 2007年5月15日

研究の目的 大量データを効率的に処理するための アルゴリズムとデータ構造の開発 アプローチ データおよびデータ構造の圧縮 局所情報のみを用いた探索 確率アルゴリズム

これまでの成果 グラフ探索アルゴリズム (論文4) 簡潔データ構造 (論文11) 分散アルゴリズムでの故障検知器 ランダムウォーク Right-Hand-on-the-Wall walk Forest search 無線ネットワークでのオンラインbroadcast 簡潔データ構造 (論文11) 透過的データ圧縮法 順序木の超簡潔データ構造 圧縮接尾辞配列・接尾辞木 実用的rank/selectデータ構造 分散アルゴリズムでの故障検知器 センサーネットワークでの省電力データ収集

問題 入力: n ノード連結グラフ G 出力: G の枝ラベル 各枝は2つのラベルを持つ (両端に1つずつ) 3 問題 入力: n ノード連結グラフ G 出力: G の枝ラベル 各枝は2つのラベルを持つ (両端に1つずつ) 各ノード v の周りのラベルは [1,deg(v)] の異なる整数 “Right-Hand-on-the-Wall” walk が存在

Right-Hand-on-the-Wall Walk エージェントがあるノードの1ラベル枝から出発 点 v に枝 i から着いたら，枝 i+1 から出る (無記憶) エージェントは全点を訪れる 1 3 2 1 1 2 2 3 3 2 3 1

結果 どんなグラフにも Right-Hand-on-the-Wall Walk が存在 walkの長さは高々 10n 参考

Forest Search 仮定 解きたい問題 グラフ全体は記憶できない ノードを訪れるとそのノードの隣接点がわかる グラフには情報を書けない ノードは異なる ID を持っている 解きたい問題 点 u を出発し v に着くまでのstep数を減らす 全点を訪れるまでのstep数を減らす 全点を少ないメモリで重複無く列挙 P2Pに有効(?)

Forest Search 逆探索の拡張 スケールフリーネットワークの探索に適している グラフに森を定義する 1つの木の中は逆探索 それぞれの木を1点に縮約したグラフでDFS 必要メモリは木の数に比例 ステップ数 O(|V|+|E|・h) （h: 木の中で最大の深さ） スケールフリーネットワークの探索に適している

スケールフリーネットワーク 次数の分布がベキ則に従う ： P(d)～d –γ 生成モデルのひとつ：BAモデル [Barabasi and Albert 99 ] Growth: 単位ステップあたり１点とそこから出る辺をm本追加 Preferential attachment: 追加する辺の一端は既存の頂点へ その次数に比例した 確率で決定する 　　　　　　　　　　　　　　　　 傾き： －γ 頂点数 次数d

仮想的な森 ネットワークの構造の 部分グラフ（spanning forest）が仮想的な森 になる forest search は 仮想的な木の構造に 従って，ネットワークを 探索する

仮想的な木を作る 親の選び方 : 単純ルール 局所情報だけで 任意の頂点の親と子を一意に 決められるため，木構造を記憶しておく必要がない 親の選び方　:　単純ルール Nk(u) : 頂点uからの距離が高々k(>=0)である頂点の集合 N１(u)から最も次数の高い頂点を頂点uの親π(u)に選ぶ ２つ以上あればその中で最もIDの小さい頂点 　 局所情報だけで 任意の頂点の親と子を一意に 決められるため，木構造を記憶しておく必要がない 各頂点 u にはちょうどひとつの親 π(u) が存在し， deg(π(u)) > deg(u) or ID(π(u)) < ID(u) (π(u)≠u) deg(π(u)) = deg(u) (π(u) =u)

仮想的な木を作る （追加ルール） 親の選び方 : 追加ルール u u 目的：仮想木を統合して木の数を減らしたい 仮想的な木を作る　（追加ルール） 親の選び方　:　追加ルール 目的：仮想木を統合して木の数を減らしたい 単純ルールで仮想木の根になる頂点uに対して，π(u)を選び直す N２(u)で最も次数の高い頂点をπ(u)に選ぶ (２つ以上あればその中でIDが最小の頂点) π(u) u u π(u) 追加ルール 単純ルール

追加ルールによって作られるグラフの性質 定理： 追加ルールによって定義されるグラフFは次の性質を満たす u １．単純ルールにおける木の根uが異なる木に属する頂点と隣接していたなら，追加ルールにおいてuは木の根ではない ２．Fには長さ２以上のサイクルは存在しない u π(u)

計算機実験 ERモデル ： ランダムグラフ [ Erdos and Renyi ] 探索手法 forest search β-random walk 　(比較対象) ネットワーク 頂点数 n， 辺数 2n ネットワーク生成モデル ERモデル　 ：　ランダムグラフ [ Erdos and Renyi ] WSモデル　：　スモールワールドネットワーク 　　　　　　　　　　　 　[ Watts and Strogatz ] BAモデル　 ：　スケールフリーネットワーク 全 n(n-1)/2 個の起点・目標頂点対に対して探索を実行し平均を取る それぞれ20個のネットワークに対する平均を取る

実験結果 ： ステップ数 （n = 500） random walk に対する性能向上の割合 探索手法 ER WS BA 平均 forest search 627 962 516 β-random walk 902 1380 1031 最大 4025 5121 2259 4886 3947 3173 random walk に対する性能向上の割合 最も高いモデル :　BA 最も低いモデル :　WS ※β-random walk はβ=0.5の結果

実験結果 ： 仮想的な森に関する量（単純ルール） 木の数 最大の木のサイズ BA BAモデル : 最大の木のサイズが大きく，木の数は少ない WSモデル : 最大の木のサイズが小さく，木の数は多い WS ER ER BA WS

実験結果 ： 仮想的な森に関する量（追加ルール） 木の数 最大の木のサイズ BAモデル : 木の数は劇的に減少 90％以上の頂点が最大の木に含まれる　

実験結果 ： cover time ネットワークの全頂点を訪れるときのステップ数 ・BAモデル ・n=~500 β-random walk forest search（単純ルール） forest search (追加ルール)

BAモデルのグラフの 生成において， 単位ステップ毎に 追加する辺の数 実験結果 : 木のサイズの分布 n=200,000 最大の木のサイズが非常に大きい 最大の木を除いて，サイズの分布はベキ則に従う ※パラメータm BAモデルのグラフの 生成において， 単位ステップ毎に 追加する辺の数 最大の木のサイズ　m=2 のとき頂点数の65パーセント。 mが増加するほど最大木のサイズは大きくなる

簡潔データ構造 (Succinct Data Structures) 簡潔データ構造＝データの簡潔表現＋簡潔索引 簡潔データ構造の例 木，グラフ 文字列 順列，関数

簡潔表現 サイズが情報理論的下限に(ほぼ)一致する表現 入力が L 通りのとき，情報理論的下限は log L bits 例1: 集合 S  {1,2,...,n} のサイズの下限 log 2n = n bits 例2: n 頂点の順序木 例3: n 文字の文字列 n log  bits (: アルファベットサイズ)

簡潔索引 決められた操作を実現するためのデータ構造 サイズ: o(log L) bits 従来の表現と(ほぼ)同じ操作時間 計算モデル: word RAM ポインタサイズ w bits (2w 個のメモリセル) w ビットの四則演算が定数時間 連続する w ビットのメモリの読み書きが定数時間 前述の例では w = log n = log log L

簡潔データ構造の例 超簡潔 (ultra-succinct) データ構造 サイズがデータのある種のエントロピーと一致 順序集合 S {1,2,...,n} 順序木 (n ノード) 情報理論的下限 n log  n 2no(n) 簡潔データ構造 (n+o(n)) log  [GV00] n+o(n) [J89][M96] 2n+o(n) [MR97] 超簡潔データ構造 nHk(S)+o(n log ) [GGV03] nH0(S)+o(n) [RRR02] nH*+o(n) [本研究] 超簡潔 (ultra-succinct) データ構造 サイズがデータのある種のエントロピーと一致 問い合わせ計算量が変わらない

新しい順序木の表現 BPとDFUDSでの基本演算は全て定数時間 サイズは木のある種のエントロピーに圧縮 定義: 木次数エントロピー 最悪 2n+o(n) ビット 定義: 木次数エントロピー ni: 次数 i のノード数 例: 全2分木 (全内部ノードが丁度2つの子を持つ) BP, DFUDS: 2n ビット 本研究: n ビット

サイズの下限 次数 i のノード数が ni である順序木の数は より，このエントロピーは木の次数を固定した場合の情報理論的下限と一致 [Rote 96]

透過的データ圧縮法 任意箇所を瞬時に復元 (log n ビットを定数時間) 圧縮率は従来通り word RAMモデルでは最適 　⇒データは圧縮されていないとみなせる 圧縮率は従来通り (全ての k  0 に対して同時に成立)

今年度の予定 Forest SearchとUSTCONNアルゴリズムの関係 簡潔データ構造の応用 V. Trifonov. An O(log n log log n) space algorithm for undirected st-connectivity, STOC 05. 簡潔データ構造の応用 頻出アイテム集合 (Web)グラフの符号化