Duplicate Detection in Probabilistic Relational Databases

Abstract

Viele Anwendungen wie Texterkennungsverfahren oder Sensornetzwerke arbeiten häufig auf ungenauen, unscharfen, oder zweifelhaften Informationen. Ein aktueller Trend in der Datenbankforschung ist es, solche Unsicherheiten als wertvollen Bestandteil des Anwendungsergebnisses zu betrachten und somit die Ausgaben dieser Anwendungen entsprechend anzureichern. Ein weit entwickeltes Werkzeug zur Modellierung von Unsicherheiten in Anwendungsdaten sind probabilistische Datenbanken. Um verschiedene, heterogene probabilistische Datenbestände zu integrieren oder um einen einzelnen probabilistischen Datenbestand von Inkonsistenzen zu bereinigen, bedarf es Verfahren, um Datenobjekte zu erkennen, die dasselbe Realweltobjekt referenzieren. Herkömmliche Verfahren zum Aufspühren solcher sogenannten Duplikate wurden bisweilen allerdings nur für Datenobjekte konzipiert, die durch einzelne, exakte Attributwerte beschrieben sind und deren Zugehörigkeit zum betrachteten Gegenstandsbereich als sicher angesehen wird. Probabilistisch modellierte Datenobjekte können jedoch mehrere Werte pro Attribut aufweisen. Zudem kann ihre Relevanz für den betrachteten Gegenstandsbereich infrage stehen. Aus diesen Gründen ist eine Verwendung herkömmlicher Duplikaterkennungsverfahren für probabilistische Datenbanken ohne wesentliche Anpassungen nicht geeignet. In dieser Dissertation widmen wir uns dem Erkennen von Duplikaten in probabilistischen relationalen Datenbanken. Der zentrale Forschungsaspekt dieser Arbeit ist dabei der Entwurf eines generischen Ansatzes, der eine Anpassung an individuelle Bedürfnisse erlaubt und somit ein Erkennen von probabilistischen Duplikaten in unterschiedlichen Anwendungsbereichen ermöglicht. Ein Vorteil probabilistischer Datenbanken ist, dass wir nicht gezwungen sind, auftretende Unsicherheiten über Duplikatsbeziehungen aufzulösen und solche Unsicherheiten stattdessen im Duplikaterkennungsergebnis modellieren können. Eine Vielzahl weit verbreiteter probabilistischer Datenmodelle, wie z.B. Tupel-unabhängige Datenbanken, sind allerdings nicht mächtig genug, um Unsicherheiten über Duplikatentscheidungen modellieren zu können. Aus diesem Grund unterscheiden wir zwischen deterministischen und indeterministischen Duplikaterkennungsverfahren. Erstere zeichnen sich dadurch aus, dass sie jegliche Unsicherheiten über Duplikatentscheidungen beseitigen, indem sie ein einziges Duplikat-Clustering als Ausgabe liefern. Das Ergebnis eines indeterministischen Verfahrens besteht hingegen aus einer Menge an möglichen Duplikat-Clusterings, die jeweils mit einer Wahrscheinlichkeit versehen sein können. Wir identifizieren zwei sinnvolle Strategien, um herkömmliche Duplikaterkennungsverfahren an die inhärenten Unsicherheiten probabilistischer Daten anzupassen. Basierend auf diesen Strategien entwerfen wir zwei generische Ansätze zur deterministischen Duplikaterkennung in probabilistischen Datenbanken und präsentieren verschiedene Techniken, um die Berechnungskomplexität dieser beiden Ansätze zu verringern. In diesem Zusammenhang entwickelen wir ein Ähnlichkeitsmaß für diskrete Wahrscheinlichkeitsverteilungen, das eine performante Alternative zur Earth Mover’s Distance darstellt. Hinsichtlich des Konzepts der indeterministischen Duplikaterkennung beginnen wir mit einer formalen Definition. Anschließend präsentieren wir verschiedene Ansätze, die es gestatten, eine Menge von möglichen Duplikat-Clusterings in einer probabilistischen Datenbank zu modellieren und diskutieren mögliche Arten und Weisen in denen ein solches Deduplizierungsergebnis verarbeitet werden kann. Zudem präsentieren wir ein Clustering-Verfahren, das eine effiziente Berechnung von indeterministischen Duplikaterkennungsergebnissen ermöglicht. Darüber hinaus betrachten wir die Bedeutung der Qualität eines Duplikaterkennungsprozesses in Anbetracht unsicherer Duplikatentscheidungen, konzipieren verschiedene Maße, um diese Qualitätsinterpretationen zu beziffern und präsentieren Methoden, um diese Maße kostengünstig zu berechnen. Den Abschluß dieser Arbeit bildet eine experimentelle Evaluierung, in der wir zunächst eine prototypische Implementierung präsentieren und dann verschiedene experimentelle Ergebnisse diskutieren.

Many applications such as OCR systems or sensor networks have to deal with uncertain information. One trend in current database research is to accept uncertainty as a ‘fact of life’ and hence to incorporate it into such applications’ results by producing probabilistic output data. To meaningfully integrate probabilistic data from multiple heterogeneous sources or to clean a single probabilistic database, duplicate database entities need to be identified. Duplicate detection has been extensively studied in the past, but conventional duplicate detection approaches are designed for matching database entities that are described by certain values and certainly belong to the considered universe of discourse. In probabilistic databases, however, each database entity can have several alternative values per attribute and its membership to the considered universe can be questionable. As a consequence, conventional duplicate detection approaches cannot be used for probabilistic databases without adaptation. In this thesis, we consider the challenge of duplicate detection in probabilistic relational databases. The central research aspect of this thesis is to develop a generic approach that enables detection of probabilistic duplicates in highly diverse application domains by allowing an adjustment to individual needs. The benefit of using a probabilistic database for modeling deduplication results is that we do not necessarily need to resolve uncertainty on duplicate decisions, but instead can incorporate emerging decision uncertainty into the output database. Nevertheless, many commonly used probabilistic representation systems, such as tuple-independent probabilistic databases, are not powerful enough to model uncertainty on duplicate decisions. For that reason, we distinguish between deterministic duplicate detection approaches that completely resolve uncertainty on duplicate decisions by producing a single duplicate clustering as a result and indeterministic duplicate detection approaches that provide a set of possible duplicate clusterings as output. We identify two meaningful strategies for adapting conventional duplicate detection approaches to the uncertainty that is inherent in probabilistic data. According to these strategies, we propose two generic approaches to deterministic duplicate detection in probabilistic databases and present several techniques for reducing their computational complexity. In this context, we develop a similarity measure for discrete probability distributions that can be used as a fast alternative to the Earth Mover’s Distance. Additionally, we formalize the concept of indeterministic duplicate detection, propose approaches for representing an indeterministic deduplication result within a probabilistic database, discuss possible ways to meaningfully process indeterministic deduplication results, and present a clustering approach that can be used to efficiently compute a set of possible clusterings. Moreover, we discuss the meaning of detection quality in the presence of uncertain duplicate decisions, present measures for rating this meaning by numbers, and propose methods to compute these measures in an efficient way. Finally, we present a prototypical implementation and the results of a set of experiments we conducted on several test databases in order to prove the concepts of our proposed approaches.