FFTED - Fast and Flexible Tree Edit Distance

Data that are structured in hierarchies are called trees. An example of tree data is the organizational hierarchy of a company with departments, their managers, and subordinate employees. Other examples include enterprise assets, bills of material, natural or computer language syntax trees, directories in file systems, or molecular structures in bioinformatics. When tree data change, new tree versions are generated. An important task is to compute the difference (called diff) between two version of a tree. A good diff is as concise as possible. A common approach to compute diffs for trees is the so-called tree edit distance (TED), which computes the minimal diff. The computation of the minimal diff is challenging. Current solutions suffer from two problems that make them impractical in many scenarios: (1) Efficiency: The computation of the minimal diff is too slow. When the tree size doubles, the runtime increase by a factor of four or more. Current techniques are applicable to hierarchies with about ten thousand elements, but many interesting trees have millions of elements (e.g., bills of material). (2) Flexibility: TED computes the most concise diff and disregards any application semantics, which may lead to non-intuitive results. For example, TED may turn a department into an employee to keep the diff small. Various attempts have been made to overcome these problems, but all solutions suffer from at least one of the following issues: quality is traded off against speed (i.e., the diffs are too verbose), often without any guarantee about the deviation from the optimal result; the application semantics are hard-wired in the solution, thus restricting its scope to very specific applications; or only one of the issues (efficiency or flexibility) is addressed. The goal of this project is to solve the efficiency and flexibility problems of TED without trading off quality. We will allow users to specify constraints that fit their application semantics as part of the input (e.g., departments cannot be turned into employees), and the minimal diff that respects these constraints will be computed. This will make our solution applicable to a wide range of different domains. In order to gain efficiency, we will exploit two observations that have received little attention in the past. First, changes between tree versions typically affect only a small portion of the tree; by focusing the computational effort on the parts that actually changed we hope to achieve considerable runtime improvements. Second, user constraints limit the number of allowable diffs, and fewer options must be considered; we plan to leverage this fact as well to gain performance. If successful, our solution will be the first one to deal with user-defined constraints and compute the minimal diff efficiently.

The goal of this project was to develop efficient techniques for similarity queries over tree data. Data items are represented as trees when the individual data values show hierarchical dependencies, for example, the name of an author belongs to the authored book and can only be interpreted in this context. Tree data are common in various application scenarios and have led to the development of popular hierarchical data formats like XML or JSON. A query of great interest retrieves trees based on their pairwise similarities, expressed as the minimal difference between two trees: the so-called tree edit distance (TED). While queries based on TED provide users with intuitive results, they are computationally challenging, calling for efficient techniques to answer such queries. This project developed a number of novel approaches for common types of tree similarity queries that advance the state of the art and outperform previous approaches in terms of runtime or memory consumption. (1) TopDiff: Computing the minimal difference between a pair of trees is a useful but expensive operation. The TopDiff algorithm developed in this project leverages the similarity of the input trees to substantially speed up the distance computation. For similar trees, the runtime of TopDiff grows only linearly in the tree size in contrast to the cubic growth of the TED algorithm. (2) SlimCone: The top-k subtree similarity query identifies the k subtrees of a document tree that are closest to a given query tree. Previous solutions were based on an indexing technique that required a large amount of memory, which limited the applicability of this solution to small instances. The SlimCone index developed in this project is based on a new idea that avoids the memory issue, scales to large instances, and returns the top-k result faster than all previous techniques. (3) TJoin: The tree similarity join identifies all tree pairs in a collection of trees that are within a user-defined TED threshold. This query is typically used to identify duplicates in a dataset. Comparing all pairs of trees does not scale to large tree collections. The TJoin algorithm introduces an index and inexpensive yet effective filters that utilize the structural information of the trees to avoid most of the pairwise TED computations. For the tree pairs that pass all filters, TJoin uses a novel verification algorithm that leverages the user-defined threshold to avoids the expensive TED computation. All techniques developed in this project have been experimentally compared to previous solutions and often outperform their competitors by several orders of magnitude in runtime for large input instances.