Windowed pq-grams for approximate joins of data-centric XML
MetadataShow full item record
SubjectHierarchical data; XML; Unordered tree; Tree distance; Similarity join; Approximate matching; pq-Grams
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-grams distance between two trees is the number of pq-grams that are in one tree decomposition only. We show that our distance is a pseudo-metric 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.
Showing items related by title, author, creator and subject.
Augsten N; Böhlen M; Gamper J (ACM, 2006)Several recent papers argue for approximate lookups in hierarchical data and propose index structures that support approximate searches in large sets of hierarchical data. These index structures must be updated if the ...
Botoeva E; Calvanese D; Rodriguez-Muro M (Springer, 2010)Ontology based data access (OBDA) is concerned with providing access to typically very large data sources through a mediating conceptual layer that allows one to improve answers to user queries by taking into account domain ...
Salvadori, G; Durante, F; Perrone, E (Société Francaise de Statistique, 2013)In this work we outline a constructive approach for the approximation of Kendall’s distribution function and Kendall’s Return Period in the bivariate case. First, we introduce a suitable theoretical framework, based on the ...