Nikolaus Augsten, Michael Böhlen, Curtis Dyreson, Johann Gamper — ICDE'08
In data integration applications, a join matches elements that are common to two data sources. Often, however, elements are represented slightly different in each source, so an approximate join must be used. For XML data, most approximate join strategies are based on some ordered tree matching technique. But in data-centric XML the order is irrelevant: two elements should match even if their subelement order varies.
In this paper we give a solution for the approximate join of unordered trees. Our solution is based on windowed pqgrams. We develop an efficient technique to systematically generate windowed pqgrams in a three-step process: sorting the unordered tree, extending the sorted tree with dummy nodes, and computing the windowed pqgrams on the extended tree. The windowed pqgram distance between two sorted trees approximates the tree edit distance between the respective unordered trees. The approximate join algorithm based on windowed pqgrams is implemented as an equality join on strings and avoids to evaluate the distance between every pair of input trees. Our experiments with synthetic and real world data confirm the analytic results and suggest that our technique is both useful and scalable.
Download Paper: [PDF]
Slides: Screen [PDF] , Printer [PDF]
Source code: [approxlib]