A Framework for XML Similarity Joins

  • A prime motivation for using XML to directly represent pieces of information is the ability of supporting ad-hoc or 'schema-later' settings. In such scenarios, modeling data under loose data constraints is essential. Of course, the flexibility of XML comes at a price: the absence of a rigid, regular, and homogeneous structure makes many aspects of data management more challenging. Such malleable data formats can also lead to severe information quality problems, because the risk of storing inconsistent and incorrect data is greatly increased. A prominent example of such problems is the appearance of the so-called fuzzy duplicates, i.e., multiple and non-identical representations of a real-world entity. Similarity joins correlating XML document fragments that are similar can be used as core operators to support the identification of fuzzy duplicates. However, similarity assessment is especially difficult on XML datasets because structure, besides textual information, may exhibit variations in document fragments representing the same real-world entity. Moreover, similarity computation is substantially more expensive for tree-structured objects and, thus, is a serious performance concern. This thesis describes the design and implementation of an effective, flexible, and high-performance XML-based similarity join framework. As main contributions, we present novel structure-conscious similarity functions for XML trees - either considering XML structure in isolation or combined with textual information -, mechanisms to support the selection of relevant information from XML trees and organization of this information into a suitable format for similarity calculation, and efficient algorithms for large-scale identification of similar, set-represented objects. Finally, we validate the applicability of our techniques by integrating our framework into a native XML database management system; in this context we address several issues around the integration of similarity operations into traditional database architectures.
  • Ein Framework für XML Similarity Joins

Download full text files

Export metadata

Additional Services

Search Google Scholar
Author:Leonardo Andrade Ribeiro
Advisor:Theo Härder
Document Type:Doctoral Thesis
Language of publication:English
Year of Completion:2010
Year of first Publication:2010
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2010/07/15
Date of the Publication (Server):2010/08/16
Tag:Duplikaterkennung; Similarity Join; XDBMS
Duplicate Identification; Similarity Joins; XDBMS
GND Keyword:Datenbank; XML; Ähnlichkeit; Algorithmus; Leistungsmessung
Faculties / Organisational entities:Kaiserslautern - Fachbereich Informatik
CCS-Classification (computer science):H. Information Systems / H.2 DATABASE MANAGEMENT (E.5)
H. Information Systems / H.3 INFORMATION STORAGE AND RETRIEVAL / H.3.3 Information Search and Retrieval
DDC-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011