文献

J-GLOBAL ID：202102279046448394   整理番号：21A0150788

GraphSDH:分布と階層を持つ一般的グラフサンプリングフレームワーク【JST・京大機械翻訳】

GraphSDH: A General Graph Sampling Framework with Distribution and Hierarchy

著者 (4件)： Hu Jingbo (BNRist, Tsinghua University,Department of Electronic Engineering,Beijing,China) ,  Dai Guohao (BNRist, Tsinghua University,Department of Electronic Engineering,Beijing,China) ,  Wang Yu (BNRist, Tsinghua University,Department of Electronic Engineering,Beijing,China) ,  Yang Huazhong (BNRist, Tsinghua University,Department of Electronic Engineering,Beijing,China)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2020  号： HPEC  ページ： 1-7  発行年： 2020年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 大規模グラフは,様々な応用において重要な役割を果たすが,長い処理時間によって制限される。グラフサンプリングは,グラフデータ量を減らし,アルゴリズムを加速する有効な方法である。しかし,以前の研究は通常グラフアルゴリズムモデルに関連した理論解析を欠いている。本研究では,一般的大規模グラフサンプリングフレームワークであるGraphSDH(分布および階層によるグラフ Samplingサンプリング)を頂点中心グラフモデルに基づいて確立した。4つの一般的サンプリング技術に従って,著者らは分散を最小にするためにサンプリング確率を導き,中間値のための事前推定過程があるかどうかに従って設計を最適化した。グラフアルゴリズムの精度をさらに改善するために,サンプリング位置解析に基づく頂点度および階層的最適化方式に基づく層状サンプリング法を提案した。大規模グラフに関する大規模な実験は,グラフSDHが元のグラフの10%のエッジだけをサンプリングすることによってPageRankのために95%以上の精度を達成して,PageRankを非サンプリングケースのものより数倍高速化することができることを示した。ランダム隣接サンプリングと比較して,グラフSDHは,20%のサンプリング近傍比率(サンプリング比率)で,PageRankの平均相対誤差を約17%減らすことができた。さらに,GraphSDHは,Breadth-First探索(BFS),交互最小二乗法(ALS)およびラベル伝搬アルゴリズム(LPA)のような様々なグラフアルゴリズムに適用できる。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  最適化 ,  加工時間 ,  高速化
準シソーラス用語： グラフアルゴリズム ,  相対誤差 ,  交互最小二乗法 ,  ラベル伝搬 ,  PageRank , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (2件)： 分布 ,  階層