文献

J-GLOBAL ID：202202231520181867   整理番号：22A1163635

MGTagによる高速可到達性クエリーサービスの提供:多次元グラフラベリング法【JST・京大機械翻訳】

Providing Fast Reachability Query Services With MGTag: A Multi-Dimensional Graph Labeling Method

著者 (5件)： Yuan Pingpeng (National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab., Cluster and Grid Computing Lab., Big Data Technology and System Lab., School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, Ch...) ,  You Yujie (National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab., Cluster and Grid Computing Lab., Big Data Technology and System Lab., School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, Ch...) ,  Zhou Shuang (National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab., Cluster and Grid Computing Lab., Big Data Technology and System Lab., School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, Ch...) ,  Jin Hai (National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab., Cluster and Grid Computing Lab., Big Data Technology and System Lab., School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, Ch...) ,  Liu Ling (College of Computing, Georgia Institute of Technology, Atlanta, GA, USA)
資料名： IEEE Transactions on Services Computing  (IEEE Transactions on Services Computing)
巻： 15  号： 2  ページ： 1000-1011  発行年： 2022年 
JST資料番号： W2437A  ISSN： 1939-1374  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 頂点が大きな有向グラフ上で他の頂点に達することができるかどうかは,可到達性質問である。それは,最も基本的なグラフオペレータの1つであり,学術学と産業の両方で研究者を引きつけて,それを研究する。主要な技術的課題は,3つの主なコスト,即ち,インデックス構築時間,インデックスサイズ,および大規模/小型/高密度グラフ上のクエリ処理時間,の効率的管理によって,高速到達可能性クエリをサポートすることである。実世界グラフはサイズが大きくなるにつれて,これらの問題は高性能ソリューションを要求する未解決の課題のままである。本論文では,高速可到達性クエリをサポートするために,マルチ次元グラフラベリングアプローチ(MGTagと呼ぶ)を提案した。MGTagは3つの側面で新規である。第1に,それはグラフを非共有グラフと呼ばれる互いに素な頂点集合,および交差エッジと呼ばれるいくつかの分割エッジを有する複数の部分グラフに再帰的に分割する。第2に,著者らは,非共有グラフにおける各頂点に対して,層の1次元,非共有グラフの1次元および間隔の2次元の4次元ラベルの1次元を構築した。最後に,4次元ラベリング方式によって,著者らは効率的に到達可能性質問に答えるアルゴリズムを設計した。28の大/小および高密度/スパースグラフに関する大規模な実験は,高次元指数の構築が,急速に,そして,インデックスサイズも,最先端の手法のほとんどと比較して,競合することを示した。結果はまた,著者らのアプローチが,大規模/小型/高密度グラフ上の到達可能性クエリに答える最先端の手法よりもスケーラブルで効率的であることを示した。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *グラフ ,  加工時間 ,  オペレータ ,  有向グラフ ,  部分グラフ ,  集合 ,  二次元 ,  一次元 ,  *高次元 ,  頂点 ,  大規模 ,  四次元
準シソーラス用語： 互いに素 ,  *クエリー , 【Automatic Indexing@JST】

分類 (2件)： パターン認識  (JE07000S) ,  自然語処理  (JE06000L)

タイトルに関連する用語 (5件)： 可到達性 ,  クエリー ,  サービス ,  多次元 ,  グラフラベリング