Not logged in.

Quick Search - Contribution

Contribution Details

Type Conference or Workshop Paper
Scope Discipline-based scholarship
Published in Proceedings Yes
Title Approximate Joins for Data-Centric XML
Organization Unit
Authors
  • Nikolaus Augsten
  • Michael Böhlen
  • Curtis Dyreson
  • Johann Gamper
Presentation Type paper
Item Subtype Original Work
Refereed Yes
Status Published in final form
Language
  • English
Page Range 814 - 823
Event Title ICDE 2008: 24th International Conference on 7-12 April
Event Type conference
Event Location Auckland, New Zealand
Event Start Date August 23 - 2008
Event End Date August 28 - 2008
Abstract Text In data integration applications, a join matches elements thatare 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 pq-grams. We develop an efficient technique to systematically generate windowed pq-grams in a three-step process: sorting the unordered tree, extending the sorted tree with dummy nodes, and computing the windowed pq-grams on the extended tree. The windowed pq-gram distance between two sorted trees approximates the tree edit distance between the respective unordered trees. The approximate join algorithm based on windowed pq-grams is implemented as an equality join on strings which avoids the costly computation of 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.
Digital Object Identifier 10.1109/ICDE.2008.4497490
Other Identification Number merlin-id:2297
PDF File Download from ZORA
Export BibTeX
EP3 XML (ZORA)