文献

J-GLOBAL ID：201802282559588023   整理番号：18A0851096

グラフ編集距離の上界計算のための新しい階層ベースフレームワーク【JST・京大機械翻訳】

A novel hierarchical-based framework for upper bound computation of graph edit distance

著者 (5件)： Gouda Karam (Faculty of Computers & Informatics, Benha University, Egypt) ,  Gouda Karam (Department of Computer & Decision Engineering, Universite Libre de Bruxelles, Belgium) ,  Arafa Mona (Faculty of Computers & Informatics, Benha University, Egypt) ,  Calders Toon (Department of Computer & Decision Engineering, Universite Libre de Bruxelles, Belgium) ,  Calders Toon (Department of Mathematics & Computer Sciences, University of Antwerp, Belgium)
資料名： Pattern Recognition  (Pattern Recognition)
巻： 80  ページ： 210-224  発行年： 2018年 
JST資料番号： D0611A  ISSN： 0031-3203  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフ類似性は多くの応用を有する重要な概念である。グラフ編集距離は,利用可能な最も柔軟なグラフ類似性測度の1つである。この測度による主な問題は,実際には,その指数的時間複雑さのために,小さなグラフに対してのみ計算できることである。本論文は,グラフ編集距離の高品質近似を有する効率的解法に関するものである。特に,グラフ編集距離のための新しい上限計算フレームワークを提示した。それはグラフの幅第一階層的ビューとグラフマッピングを構築するための新しい階層的トラバースとマッチング法に基づいている。このフレームワークの主な利点は,地図構築と編集計算を容易で直接的な方法で組み合わせることである。それはまた,結合を改善するために異なる階層的視点からグラフを比較することを可能にした。さらに,多視点比較の複雑さを避け,距離精度を保存するために,頂点とエッジ星構造に基づく2つの新しい視点選択法を導入して,計算をスケールした。最先端の過大評価法による著者らのアプローチと対照的に,実験は,それが,実際のデータグラフ上で3桁の大きさの高速化と同等の上限を提供することを示した。また,実験により,この手法が,最先端の過大評価法と比較して,KNN分類器の分類精度を15%以上改善することを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *編集 ,  マッチング ,  *グラフ ,  測度 ,  類似性 ,  近似法 ,  高速化
準シソーラス用語： 分類精度 ,  評価法 ,  選択法 ,  トラバース ,  高品質 ,  *上界 ,  *編集距離 , 【Automatic Indexing@JST】

著者キーワード (3件)： グラフ類似性 ,  グラフ編集距離 ,  上界

分類 (2件)： パターン認識  (JE07000S) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (6件)： グラフ ,  編集距離 ,  上界 ,  計算 ,  階層 ,  フレームワーク