Physical Sciences and Mathematics Commons^™

Windowed Pq-Grams For Approximate Joins Of Data-Centric Xml, Nikolaus Augsten, Michael H. Böhlen, Curtis Dyreson, Johann Gamper

Curtis Dyreson

In data integration applications, a join matches elements that are common to two data sources. Since elements are represented slightly different in each source, an approximate join must be used to do the matching. For XML data, most existing approximate join strategies are based on some ordered tree matching technique, such as the tree edit distance. In data-centric XML, however, the sibling order is irrelevant, and two elements should match even if their subelement order varies. Thus, approximate joins for data-centric XML must leverage unordered tree matching techniques. This is computationally hard since the algorithms cannot rely on a predefined …