## Windowed pq-grams for approximate joins of data-centric XML

*
Nikolaus Augsten, Michael Böhlen, Curtis Dyreson, Johann Gamper
* - VLDBJ'12

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 sibling order.

In this paper, we give a solution for approximate joins based on
*unordered* tree matching. The core of our solution are
*windowed pq-grams*, which are small subtrees of a specific shape.
We develop an efficient technique to generate windowed *pq*-grams
in a three-step process: sort the tree, extend the sorted tree with dummy
nodes, and decompose the extended tree into windowed *pq*-grams.
The windowed *pq*-gram distance between two trees is the number of
*pq*-grams that are in one tree decomposition only. We show that our
distance is a pseudometric and empirically demonstrate that it effectively
approximates the unordered tree edit distance. The approximate join using
windowed *pq*-grams can be efficiently implemented as an equality
join on strings, which avoids the costly computation of the distance
between every pair of input trees. Experiments with synthetic and real
world data confirm the analytic results and show the effectiveness and
efficiency of our technique.