Design of the fast computable similarities for tree-structured data and their extension to several discrete structures

该研究引入了一种新的树编辑距离层次结构，改进了计算无序树编辑距离的MAXSNP难度，并改进了无序树编辑距离易于处理的时间复杂性。同时引入了有序树编辑距离的下界为常系数的局部频率距离和二叉树编码在二次时间内运行的串编辑距离，该距离的上下界和下界均为常数。并在此基础上设计了树形核。

This research introduced a new hierarchy of the tree edit distance and improved both the MAXSNP-hardness of computing the unordered tree edit distance and the time complexity for the tractable variations of it. Also it introduced both the local frequency distance, which runs in linear time, with constant factor lower bound of the ordered tree edit distance and the string edit distance of binary tree codes, which runs in quadratic time, with both the constant factor lower bound and the upper bound. Furthermore, it designed the tree kernel based on them.