大量ー処理领域効率良

書式設定,書式設定,第,2,第,3,第,4,第,5,*,*,*,C11:大量処理領域効率良,定兼 邦彦,小野 廣隆 山下 雅史,(,九大,),2007年5月15日,研究目的,大量効率的処理構造開発,構造圧縮,局所情報用探索,確率,2,成果,探索,(,論文,4),Right-Hand-on-the-Wall walk,Forest search,無線,broadcast,簡潔構造,(,論文,11),透過的圧縮法,順序木超簡潔構造,圧縮接尾辞配列接尾辞木,実用的,rank/select,構造,分散故障検知器,省電力収集,3,問題,入力,:,n,連結,G,出力,:,G,枝,各枝2持,(,両端1,),各,v,周,1,deg(,v,),異整数,“Right-Hand-on-the-Wall”walk,存在,1,2,3,1,3,2,1,2,3,1,2,3,4,Right-Hand-on-the-Wall Walk,1枝出発,点,v,枝,i,着，枝,i,+1,出,(,無記憶,),全点訪,2,3,1,3,2,1,1,2,3,1,2,3,5,結果,Right-Hand-on-the-Wall Walk,存在,walk,長高,10,n,参考,木定義上探索,walk,長,4,n,，3状態必要,6,Forest Search,仮定,全体記憶,訪隣接点,情報書,異,ID,持,解問題,点,u,出発,v,着,step,数減,全点訪,step,数減,全点少重複無列挙,P2P有効,(?),7,Forest Search,逆探索拡張,森定義,1木中逆探索,木1点縮約,DFS,必要木数比例,数,O(|,V,|+|,E,|,h,)（,h,:木中最大深）,探索適,8,次数分布則従：,P(,d,),d,生成：,BA,Barabasi,and Albert,99,Growth:,単位点出辺,m,本追加,Preferential attachment:,追加辺一端既存頂点 次数,比例,確率決定,次数,d,傾：,頂点数,9,仮想的森,構造,部分（spanning,forest）仮想的森,forest search,仮想的木構造,従，,探索,10,仮想的木作,親選方,:,単純,N,k,(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,),11,仮想的木作（追加）,親選方,:,追加,目的：仮想木統合木数減,単純仮想木根頂点,u,対，,(u,),選直,N,(u),最次数高頂点,(u,),選,(,以上中,ID,最小頂点,),単純,追加,u,u,(u,),(u,),12,追加作性質,定理：,追加定義F次性質満,単純木根u異木属頂点隣接，追加u木根,F長以上存在,u,(u,),13,計算機実験,探索手法,forest search,-random walk,(,比較対象,),頂点数,n,，辺数,2,n,生成,ER,：,Erdos,and,Renyi,WS,：,Watts and,Strogatz,BA,：,全,n,(,n,-1)/2,個起点目標頂点対対探索実行平均取,20,個対平均取,14,実験結果：数（,n,=500）,random walk 対性能向上割合,最高:,BA,最低:WS,探索手法,ER,WS,BA,平均,forest search,627,962,516,-random walk,902,1380,1031,最大,forest search,4025,5121,2259,-random walk,4886,3947,3173,-random walk=0.5結果,15,実験結果：仮想的森関量（単純）,BA :,最大木大，木数少,WS:最大木小，木数多,木数,最大木,ER,WS,ER,WS,BA,BA,16,実験結果：仮想的森関量（追加）,BA :木数劇的減少90以上頂点最大木含,木数,最大木,17,実験結果：,cover time,全頂点訪数,BA,n,=500,-random walk,記憶有-random walk,forest search（単純）,forest search(追加),18,実験結果:木分布,最大木非常大,最大木除，分布則従,n,=200,000,m,BA生成，単位毎追加辺数,19,簡潔構造,(Succinct Data Structures),簡潔構造簡潔表現簡潔索引,簡潔構造例,木，,文字列,順列，関数,20,簡潔表現,情報理論的下限,(,),一致表現,入力,L,通，情報理論的下限,log,L,bits,例,1:,集合,S,1,2,.,n,下限,log 2,n,=,n,bits,例,2:,n,頂点順序木,例,3:,n,文字文字列,n,log bits(:,),21,簡潔索引,決操作実現構造,:,o(log,L,)bits,従来表現,(,),同操作時間,計算,:word RAM,w,bits(2,w,個,),w,四則演算定数時間,連続,w,読書定数時間,前述例,w,=log,n,=log,log,L,22,簡潔構造例,文字列,S,(,n,文字,),順序集合,S,1,2,.,n,順序木,(,n,),情報理論的下限,n,log,n,2,n,o(,n,),簡潔構造,(,n,+o(,n,)log,GV00,n,+o(,n,),J89M96,2,n,+o(,n,),MR97,超簡潔構造,nH,k,(,S,),+,o(,n,log,),GGV03,nH,0,(,S,)+o(,n,),RRR02,nH,*+,o(,n,),本研究,超簡潔,(ultra-succinct),構造,種一致,問合計算量変,23,新順序木表現,BP,DFUDS,基本演算全定数時間,木種圧縮,最悪,2,n,+o(,n,),定義,:,木次数,n,i,:,次数,i,数,例,:,全,2,分木,(,全内部丁度,2,子持,),BP,DFUDS:2,n,本研究,:,n,24,下限,次数,i,数,n,i,順序木数,，木次数固定場合情報理論的下限一致,Rote 96,25,透過的圧縮法,任意箇所瞬時復元,(log,n,定数時間,),word RAM,最適,圧縮,圧縮率従来通,(,全,k,0,対同時成立,),26,今年度予定,Forest Search,USTCONN,関係,V.,Trifonov,.An,O(log,n log,log,n)space algorithm for undirected,st,-connectivity,STOC 05.,簡潔構造応用,頻出集合,(Web),符号化,27,