差分検出分野で有名なGumTreeの論文．

ソフトウェア進化の理解には，差分の理解が重要である． 既存の有名な差分表示方法にはUnixのdiffがある． diffは行単位で差分を出力する． しかし，行単位の差分は粗粒度なうえにプログラムの構造を無視しているため理解しにくい． また，差分の表現方法もaddとdeleteしかない．

そのような問題点を解決するため，著者らは抽象構文木(AST)のノード単位で差分を出力する手法を提案し，GumTreeとして実装した． GumTreeはASTのノード単位での差分を出力するため，プログラムの構造を無視した差分は出力されない． また，差分の表現方法もaddとdeleteに加えてupdateとmoveがある．

GumTreeでは同じファイルの2つの異なるバージョンを入力として受け取る． GumTreeでは，初めにバージョン間での各ASTノードのマッピングを行い，次にその結果を用いて差分の計算を行う． 差分の計算は既存手法をそのまま流用しているので，本文中での説明はなかった．

ノードのマッピングではtop-downフェーズとbottom-upフェーズで構成されている． ちなみに，マッピングの移動の計算はNP困難であるため，ヒューリスティクスを用いている． 全体としては，ASTのノード数をnとするとO(n^2)で計算できるらしい．

top-downフェーズでは閾値以上の高さを持つ，完全に一致したノードをマッピングする． 各ノードにはハッシュ値が振られているため，一致判定はO(1)で行える．

bottom-upフェーズでは，top-downフェーズでマッピングされたノードの親ノードの内，ある程度の類似度を持つノードをマッピングする． 最後に，マッピングされたノードの子孫ノードのうち，まだマッピングされておらず，かつマッピングできそうなものをマッピングする．

マッピング処理はまだまだ甘く，不正確な場合が多いらしい（先輩談）．