大規模グラフサンプリングと並行したノードID再配置の分割実行によるグラフ演算の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2022-03-03
• タイトル: 大規模グラフサンプリングと並行したノードID再配置の分割実行によるグラフ演算の高速化
• タイトル / 言語: en
• タイトル: Speed Up Graph Processing by Combining Graph Reordering and Sampling from Large Graphs
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: セッション3
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 慶應義塾大学大学院理工学研究科
• 著者所属: 慶應義塾大学理工学部／慶應義塾大学デジタルメディア・コンテンツ統合研究センター
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Keio University / Research Institute for Digital Media Content, Keio University
• 著者名: 土田, 康平; 金子, 晋丈
• 著者名(英): Kohei, Tsuchida; Kunitake, Kaneko
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，大規模グラフの高速解析を目的として，サンプリングで得た部分グラフを対象に演算することが一般的である．このとき，サンプリングにより部分グラフのノード ID の連続性が損なわれるため，キャッシュミスによる演算速度の低下が招かれる．部分グラフのノード ID の再配置は効果的だが，既存手法を適用するにはサンプリングの完了を待つ必要があり，大きな時間コストが発生する．そこで，サンプリングと並行して ID 再配置を分割実行する手法として WalkOrder を提案する．具体的には，Metropolis-Hastings Random Walk によるサンプリングの過程で新規ノードへの訪問数が閾値を超えるたびに，それらのノード集合から構成される部分グラフで Gorder を踏襲した再配置を行う．実世界のグラフデータセットを用いた実験により，サンプリング後に再配置を行わない場合およびサンプリング後に Gorder を適用した場合の両者と比較し，サンプリング開始時点からグラフ演算終了時点までの総所要時間が減少したことを示した．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11135936
• 書誌情報: 研究報告知能システム（ICS）; 巻 2022-ICS-206, 号 13, p. 1-8, 発行日 2022-03-03
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-885X
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会