文献

J-GLOBAL ID：201702277305717086   整理番号：17A0238815

1000000000スケールのグラフのための効率的な三角形リスト【Powered by NICT】

Efficient triangle listing for billion-scale graphs

著者 (5件)： Zhang Hao (State Key Laboratory of Software Engineering, Wuhan University, China) ,  Zhu Yuanyuan (State Key Laboratory of Software Engineering, Wuhan University, China) ,  Qin Lu (Centre for Quantum Computation and Intelligent Systems, University of Technology, Sydney, Australia) ,  Cheng Hong (The Chinese University of Hong Kong, Hong Kong, China) ,  Yu Jeffrey Xu (The Chinese University of Hong Kong, Hong Kong, China)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2016  号： Big Data  ページ： 813-822  発行年： 2016年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文では,古典的な三角形リスト問題,エッジによってお互いに接続された三頂点のすべてのタプルを列挙を目指したについて述べた。この問題は内部および外部メモリにおける集中的に研究されているが,ネットワーク上の複数の機械は,良好な性能とスケーラビリティを達成するために利用できる,分散環境における緊急の課題である。分散環境における事実上の計算法の一つとして,MapReduceは,既存の三角形リストアルゴリズムのいくつかで使用されている。しかし,これらのアルゴリズムは,通常,大量の中間データの大規模グラフ上のスケーラビリティを妨げる大きなを再編成する必要がある。本稿で著者等は,MapReduce,FTLにおける新しい三角形リストアルゴリズム,シャッフル段階中に移動した中間データを大幅に低減する軽量データ構造を利用することを提案し,十億スケールでグラフを扱う場合に記憶とネットワーク帯域幅の負荷を容易にする多重ラウンド技術を備えている。中間データのサイズはグラフにおける三角形の数に井戸近くで有界であることを証明した。各ラウンドでシャッフルサイズをさらに低減するために,ここではまた,中間データ,2/3までの空間を節約できるを貯蔵するコンパクトなデータ構造を考案した。広範な実験を行いその結果,提案アルゴリズムは,大規模な実世界グラフ上の数倍に既存の競争相手よりも優れていることを示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： アルゴリズム ,  帯域幅 ,  ネットワーク ,  再編成 ,  多重化 ,  *データ構造 ,  外部記憶装置
準シソーラス用語： 有界 ,  軽量 ,  MapReduce ,  分散環境 , 【Automatic Indexing@JST】

分類 (4件)： データベースシステム  (JD03030U) ,  計算機システム開発  (JD02010R) ,  人工知能  (JE08000Z) ,  計算機網  (JC03000K)

タイトルに関連する用語 (4件)： スケール ,  グラフ ,  三角形 ,  リスト