【文件属性】：
文件名称：Indexing for Subtree Similarity-Search using Edit Distance
文件大小：2.44MB
文件格式：PDF
更新时间：2017-03-10 03:02:31
Similarity Search
sigmod2013；ABSTRACT
Given a tree Q and a large set of trees T = fT1; : : : ; Tng, the
subtree similarity-search problem is that of nding the subtrees
of trees among T that are most similar to Q, using the
tree edit distance metric. Determining similarity using tree
edit distance has been proven useful in a variety of application
areas. While subtree similarity-search has been studied
in the past, solutions required traversal of all of T , which
poses a severe bottleneck in processing time, as T grows
larger. This paper proposes the rst index structure for subtree
similarity-search, provided that the unit cost function
is used. Extensive experimentation and comparison to previous
work shows the huge improvement gained when using
the proposed index structure and processing algorithm.