Webスケールグラフ上の実時間インデックスフリー単一ソースSimRank処理【JST・京大機械翻訳】

Shi Jieming; Jin Tianyuan; Yang Renchi; Xiao Xiaokui; Yang Yin

プレプリント

J-GLOBAL ID：202202210603629085 整理番号：22P0113559

Webスケールグラフ上の実時間インデックスフリー単一ソースSimRank処理【JST・京大機械翻訳】

Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (5件)： , , , ,
資料名：
発行年： 2020年02月19日プレプリントサーバーでの情報更新日： 2020年02月19日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

GにおけるグラフGとノードuを与えて,単一ソースSimRankクエリは,Gにおけるuとあらゆるノードvの間の類似性を評価する。単一ソースSimRank計算に対する既存の手法は,長い問い合わせ応答時間,あるいは高価な事前計算のいずれかを繰り返し,グラフGが変化するとき,再び実行する必要がある。その結果,(i)問い合わせ処理が実時間で行われなければならないシナリオに対して,そして(ii)根底にあるグラフGは,頻繁な更新で,大規模である。これに動機づけられて,筆者らは,事前計算なしに単一ソースSimRankクエリを回答する新しいアルゴリズムであるSimPushを提案し,同時に,最速既知のインデックスベース解よりも有意に高いクエリ処理速度を達成した。さらに,SimPushは厳密な結果品質保証を提供し,その高性能は基礎となるグラフの強い仮定に依存しない。特に,既存の方法と比較して,SimPushは,(i)クエリに関連する少数のノードの同定と,(ii)これらのノードのみから,(ii)計算統計量と,残差プッシュの遂行に焦点を当てた,根本的に異なるアルゴリズム設計を採用した。著者らは,SimPushの正当性を証明して,その時間複雑性を解析して,既存の方法のものによってその漸近性能を比較した。一方,SimPushの実際的性能を,8つの実データセットに関する広範囲な実験を通して評価した。結果は,SimPushが一貫してすべての既存の解を,しばしば1桁以上凌駕することを示した。特に,商品機械では,SimPushは,0.00035の経験的誤差で,133百万ノードと5.4億のエッジを含むWebグラフ上の単一ソースSimRankクエリを,0.00035の経験的誤差で,一方,最速のインデックスベースの競争者は1.18秒を必要とする。【JST・京大機械翻訳】

, , , , , , , , , ,
, , , , , 【Automatic Indexing@JST】

グラフ理論基礎 , 人工知能

, , , , ,

前のページに戻る