大量ー処理领域効率良

《大量ー処理领域効率良》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、C11:大量データ処理のための領域効率の良いアルゴリズム定兼邦彦小野廣隆山下雅史(九大)2007年5月15日研究の目的大量データを効率的に処理するためのアルゴリズムとデータ構造の開発アプローチデータおよびデータ構造の圧縮局所情報のみを用いた探索確率アルゴリズム2これまでの成果グラフ探索アルゴリズム(論文4)ランダムウォークRight-Hand-on-the-WallwalkForestsearch無線ネットワークでのオンラインbroadcast簡潔データ構造(論文11)透過的データ圧縮法順序木の超簡潔データ構造圧縮接尾辞配列・接尾辞木実用的rank/se

2、lectデータ構造分散アルゴリズムでの故障検知器センサーネットワークでの省電力データ収集3問題入力:nノード連結グラフG出力:Gの枝ラベル各枝は2つのラベルを持つ(両端に1つずつ)各ノードvの周りのラベルは[1,deg(v)]の異なる整数“Right-Hand-on-the-Wall”walkが存在1231321231234Right-Hand-on-the-WallWalkエージェントがあるノードの1ラベル枝から出発点vに枝iから着いたら，枝i+1から出る(無記憶)エージェントは全点を訪れる2313211231235結果どんなグラフにもRight-Han

3、d-on-the-WallWalkが存在walkの長さは高々10n参考グラフに木を定義してその上を探索するならwalkの長さは4nだが，エージェントは3つの状態が必要6ForestSearch仮定グラフ全体は記憶できないノードを訪れるとそのノードの隣接点がわかるグラフには情報を書けないノードは異なるIDを持っている解きたい問題点uを出発しvに着くまでのstep数を減らす全点を訪れるまでのstep数を減らす全点を少ないメモリで重複無く列挙P2Pに有効(?)7ForestSearch逆探索の拡張グラフに森を定義する1つの木の中は逆探索それぞれの木を1点に縮約し

4、たグラフでDFS必要メモリは木の数に比例ステップ数O(

5、V

6、+

7、E

8、・h)（h:木の中で最大の深さ）スケールフリーネットワークの探索に適している8スケールフリーネットワーク次数の分布がベキ則に従う　：P(d)～d–γ生成モデルのひとつ：BAモデル[BarabasiandAlbert99]Growth:単位ステップあたり１点とそこから出る辺をm本追加Preferentialattachment:追加する辺の一端は既存の頂点へその次数に比例した確率で決定する次数d傾き：－γ頂点数9仮想的な森ネットワークの構造の部分グラフ（spanningforest）が仮想的

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

10、想的な木を作る　（追加ルール）親の選び方:追加ルール目的：仮想木を統合して木の数を減らしたい単純ルールで仮想木の根になる頂点uに対して，π(u)を選び直すN２(u)で最も次数の高い頂点をπ(u)に選ぶ(２つ以上あればその中でIDが最小の頂点)単純ルール追加ルールuuπ(u)π(u)12追加ルールによって作られるグラフの性質定理：追加ルールによって定義されるグラフFは次の性質を満たす１．単純ルールにおける木の根uが異なる木に属する頂点と隣接していたなら，追加ルールにおいてuは木の根ではない２．Fには長さ２以上のサイクルは存在しないuπ(u)13計算機実験探索

11、手法forestsearchβ-randomwalk(比較対象)ネットワーク頂点数n，辺数2nネットワーク生成モデルERモデル　：　ランダムグラフ[ErdosandRenyi]WSモデル　：　スモールワールドネットワーク[WattsandStrogatz]BAモデル　：　スケールフリーネットワーク全n(n-1)/2個の起点・目標頂点対に対して探索を実行し平均を取るそれぞれ20個のネットワークに対する平均を取る14実験結果：ステップ数　（n=500）randomwalkに対する性能向上の割合最も高いモデル:BA最も低いモデル:　WS探索手法ERWSBA平均f

12、orestsearch627962516β-randomwalk9