大規模ツリーのための最小編集ベース拡散【JST・京大機械翻訳】

Pawlik Mateusz; Augsten Nikolaus

文献

J-GLOBAL ID：202002235560113623 整理番号：20A2461541

大規模ツリーのための最小編集ベース拡散【JST・京大機械翻訳】

Minimal Edit-Based Diffs for Large Trees

出版者サイト複写サービスで全文入手
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A2461541&from=J-GLOBAL&jstjournalNo=D0698C") }}

著者 (2件)： ,
資料名：
号： CIKM ’20 ページ： 1225-1234 発行年： 2020年
JST資料番号： D0698C 資料種別：会議録 (C)
記事区分：原著論文発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

階層構造データは一般にツリーとして表現され,XMLやJSONのような一般的なデータフォーマットを与えられた。興味ある問い合わせは,1つの木を木編集距離として一般的に知られている,ノード編集(欠失,挿入,ラベルレンマ)の最小集合として表現される,木の2つのバージョン間の差を計算する。残念なことに,最速の木編集距離アルゴリズムは,立方時間と二次空間で実行して,したがって,大きな入力のために実行可能でなかった。本論文では,ツリーの2つのバージョン間の差異が,概して,全体のツリーサイズより非常に小さいという事実を利用した。類似樹木の木サイズにおいて線形である新しいツリー編集距離アルゴリズムを提案した。著者らのアルゴリズムは,トップノードペアの新しい概念に基づき,冗長距離計算を避けて,ツリー拡散のための以前の解法による主要な問題であった。大規模合成および実世界ツリーに関する提案アルゴリズムの実行時間を経験的に評価した。提案アルゴリズムは,しばしば,大きさが桁の最先端技術よりも明らかに優れている。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

, , , ,
, , , , 【Automatic Indexing@JST】

著者キーワード (4件)： , , ,

グラフ理論基礎 , 計算理論

, ,

前のページに戻る