Approximate Matching of Hierarchical Data

In partial fulfillment of the terms for obtaining the Ph.D. degree, Nikolaus Augsten will give a lecture on the following subject:

“Approximate Matching of Hierarchical Data”
Friday 11th of January 2008, 14.00 in room 02.13 SL300

The goal of this thesis is to design, develop, and evaluate new methods for the approximate matching of hierarchical data represented as labeled trees. In approximate matching scenarios two items should be matched if they are similar. Computing the similarity between labeled trees is hard as in addition to the data values also the structure must be considered. A well-known measure for comparing trees is the tree edit distance. It is computationally expensive and leads to a prohibitively high run time. Our solution for the approximate matching of hierarchical data are pq-grams.

The members of the evaluation committee are: Christian S. Jensen (internal member, chair), O. Peter Buneman, University of Edinburgh, and Stefano Ceri, Politecnico di Milano.