抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフストリームの全てのエッジを貯蔵できないならば,エッジは,accuratelyCounting三角形(すなわち,長さ三のサイクル)を三角形数を推定するために蓄えなければならない社会的ネットワーク解析,Webマイニング,異常検出などの多くの用途を有する基本的なグラフ問題である。最近,限られたスペースに伴う流動環境における大域的および局所的三角形数を正確に推定するためになされている。既存の方法は,エッジの時間的依存性を考慮しないサンプリング技術を用いるが,実際の動的グラフにおける時間的局所性を観測した。すなわち,将来の端は古いエッジよりも最近のエッジを持つ三角形を形成するようであった。本研究では,大域的および局所的三角形計数のための待合室サンプリング(WRS)と呼ばれる単一パスストリーミングアルゴリズムを提案した。WRSは待合室で最も最近のエッジ,将来端で三角形を形成するようで,貯蔵常にによる時間的局所性を利用し,残りのエッジのためのリザーバサンプリングを用いた。我々の理論的及び実験的解析はWRSである:(a)高速と「いつ」:ラン線形時間で,新しいエッジの到来が推定値を維持し,更新常に,(b)有効性:最良の競争者よりも47%までより小さい推定誤差をもたらし,および(c)理論的には正しいが,時間的局所性のもとでの小さな分散を用いた非バイアス推定値を与えることを示した。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】
