Duplicate detection is the problem of detecting different entries in a data source representing the same real-world entity. While research abounds in the realm of duplicate detection in relational data, there is yet little work for duplicates in other, more complex data models, such as XML. In this paper, we present a generalized framework for duplicate detection, dividing the problem into three components: candidate definition defining which objects are to be compared, duplicate definition defining when two duplicate candidates are in fact duplicates, and duplicate detection specifying how to efficiently find those duplicates. Using this framework, we propose an XML duplicate detection method, DogmatiX, which compares XML elements based not only on their direct data values, but also on the similarity of their parents, children, structure, etc. We propose heuristics to determine which of these to choose, as well as a similarity measure specifically geared towards the XML data model. An evaluation of our algorithm using several heuristics validates our approach. Duplicate detection is the problem of determining that different representations of entities in a data source actually represent the same real-world entity. The most prominent application area for duplicate detection is customer relationship management (CRM), where multiple entries of the same customer can result in multiple mailings to the same person, incorrect aggregation of sales to a certain customer, etc. Other application areas include bioinformatics, catalog integration, and in general any domain where independently collected data is integrated. The problem has been addressed extensively for relational data stored in tables. However, more and more of today's data is represented in non-relational form. In particular, XML is increasingly popular, especially for data published on the Web and data exchanged between organizations. Conventional methods do not trivially adapt, so there is a Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. need for methods to detect duplicate objects in nested XML data. XML data is semi-structured and is organized hierarchically. This complicates the object identification task, compared to relational data that is flat and usually wellstructured. We face two problems: object definition and structural diversity. Object definition refers to the problem of defining which data values actually describe an object, i.e., which values to consider when comparing two objects. Methods for relational duplicate detection assume that each tuple represents an object and all attribute values describe that object. Sufficiently similar data values of two tuples imply that they are duplicates. This is not the case in XML: It is not clear whether a child element represents part of the description of an element (as does a relational attribute), or if it represents a related object (as does a relationship with another table). For instance, an XML element <Artist> has elements <AID>, <name>, and some <CD> elements as direct children, and every <CD> nests <CDID> and <title>. Among all these nested XML elements, it is not clear how to distinguish actual objects (i.e., artists and CDs) from elements merely describing these objects. In this paper we present a means to explicitly specify which XML elements are objects, which XML elements describe the objects, and we present some heuristics to find them automatically. Structural diversity, the second problem, addresses the fact that unlike tuples, XML elements describing the same kind of object are not necessarily equally structured. These structural differences are due to either different representations of same objects (e.g., persons may be represented as managers or employees), or differences allowed by the schema, e.g., multiplicities of elements (e.g., persons having no, one, or multiple phone numbers). Whereas different structures due to the first reason may be reconciled through schema matching techniques, the second reason is in the nature of semi-structured data and defeats conventional duplicate detection approaches for relations. This paper makes three contributions:
Weis and Naumann REF propose an XML similarity measure for a duplicate detection framework.
DogmatiX tracks down duplicates in XML
SIGMOD '05
Computer Science