Suchraumbestimmung

      Suchraumbestimmung

          Suchraumbestimmung

              Suchraumbestimmung

                  Suchraumbestimmung

                      Suchraumbestimmung

                          Suchraumbestimmung

                              Aus Gr√ľnden der Effizienz und Skalierbarkeit soll ein Vergleich aller Tupel in jeder Relation verhindert werden. Analog zu Schritt 2 aus dem Abschnitt "Strukturanalyse"  wird daher f√ľr jeden Datensatz der Suchraum zur Ableitung m√∂glicher Abbildungen begrenzt.

                              Da in der Menge A√óB im Allgemeinen viel mehr Nicht-Treffer als Treffer zu erwarten sind (u(γ)≫m(γ)), werden f√ľr einen Datensatz die Vergleichsdatens√§tze entfernt, welche auf keinen Fall zutreffen. Eine Vielzahl von Methoden haben als Aufgabe, die Rechenkosten der Namensfindung gering zu halten, indem eine erste Grobauswahl aus dem Gesamtdatenbestand isoliert wird. Sets von geordneten Paaren , auf denen der Fellegi-Sunter Verlinkungsalgorithmus Anwendung findet, sind daher mit „Blockierkriterien“ bzw. Sortierschl√ľssel belegt.

                              Man nehme als Beispiel ein Tupel-Set, in welchem eine Telefonnummer vorhanden ist. Diese Telefonnummer kann in Verbindung mit einigen wenigen Zeichen des Namens zur Bestimmung von Verlinkungen nutzen. Bei anderen Paaren mögen zusätzlich die Informationen zu Straßennamen und Stadtnamen zugrunde gelegt werden.

                              Der traditionelle Blockier-Algorithmus gruppiert Datens√§tze, wenn diese den selben Inhalt in einer Blockiervariable besitzen, also bspw. den identischen Eintrag f√ľr Stadt und Nachname in einem Datensatz. Blockierkriterien m√ľssen dabei gut gew√§hlt werden, da bei zu allgemeinen Auswahlschl√ľsseln die Menge n√§her zu untersuchender Datens√§tze zu hoch ist (korrekte Negative), bei einer zu engen jedoch passende Datens√§tze ausgesperrt bleiben k√∂nnten (falsche Positive).

                              SVG - Suchraumbestimmung - Grobblocking

                              Ebenfalls muss die Fehler-Charakteristik des gew√§hlten Schl√ľssels bekannt und ein Fehlerauftritt minimal sein. Durch die Verwendung multipler Blockierschl√ľssel kann der Fehler in einem der Schl√ľssel abgemildert werden. Die Berechnungskomplexit√§t ist pro gew√§hlten Schl√ľssel, O(h(n)+n¬≤/b), wobei h(n) = n log n bei sortierter Blocking-Menge, h(n) = n bei blocking durch hashing. Die Ergebnissmengen sind allerdings nur schwer abzusch√§tzen.

                              Eine Weiterentwicklung stellt die Sorted-Neighbourhood- oder Fenster- Strategie ("windowing strategy") nach [HS95] dar. Sie sortiert einen Datenbestand nach dem Schl√ľssel ("Key")-Attribut mit dem gr√∂√üten Unterschied und vergleicht alle Records innerhalb eines fliessenden Fensters („sliding Window“) in der aussortierten Ordnung . Die Effektivit√§t dieses Ansatzes h√§ngt stark von der Qualit√§t des gew√§hlten Schl√ľssels ab.

                              Poor chosen keys will result in a poor quality merge

                              Die „Sorted-Neighbourhood“-Methode kann in 3 Phasen zusammengefasst werden:

                              1. Erstellen der Schl√ľssel: Errechne einen Schl√ľssel f√ľr jeden Datensatz in der Liste durch extrahieren relevanter Felder oder Feldbestandteile
                              2. Sortierung der Daten: Sortiere die Datens√§tze in der Datenliste unter Nutzung des Schl√ľssels aus Schritt 1
                              3. Vereine: Bewege ein Fenster mit konstanter Gr√∂√üe durch die sequentielle Liste der Datens√§tze und limitiere den Vergleich auf passende Werte auf solche innerhalb des Fensters. Falls die Fenstergr√∂√üe w Datens√§tze umfasst, so wird jeder neuer Datensatz mit den vorhergehenden w-1 S√§tzen verglichen, um „passende Datens√§tze“ zu finden. Der erste Datensatz im Fenster slided dabei aus dem Fensterbereich.
                              SVG - Suchraumbestimmung - Sliding Window

                              Bei sehr gro√üen Datenmengen empfiehlt sich ein vorheriges Clustern des Datenbestandes. Dabei wird der Datenbestand in Sequenzen durchsucht, wobei ein n-attributiger Schl√ľssel (Bsp. Nachname+1.Buchstabe des Vornamens) extrahiert und in den n-dimensionalen Clusterraum abgebildet wird.

                              Da auch dieses gew√§hlte Attribut einen Fehler besitzen kann, ist ein einzelnes Schl√ľsselattribut zu wenig. Um demnach Fehler im Hauptschl√ľssel auszuschlie√üen, schl√§gt [HS95] folgende Methoden vor:

                              1. Durch die Vergrößerung des sliding-windows werden mehr Datensätze mit eingeschlossen.
                              2. ein mehrmaliges Ausf√ľhren mit unterschiedlichen Schl√ľsseln und relativ kleinem Fenster gibt, nach einzelnem Abgleich der Ergebniss-Gruppen und transitivem Schlie√üen (nur bei geringer Fenstergr√∂√üe empfehlenswert) die besseren Ergebnisse.

                              Als Grenzwerte sind hier die Schl√ľsselanzahl j sowie die Fenstergr√∂√üe w anzugeben. Damit errechnet sich f√ľr n Datens√§tze eine Komplexit√§t von O(i=0j(nlogn+wn)) , wobei O(nlogn) f√ľr die Sortierung ben√∂tigt wird.

                              Diese Methode basiert auf Bigramme (in [SprachSynth06] auch Diphone oder Halblaute genannt). Die Grundidee dabei besteht darin, dass nach der Indexerstellung die Werte der Blockiervariablen in eine Liste von Bigramme (Diphone, Halblaute) konvertiert werden, welche alphabetisch sortiert und von Duplikaten bereinigt werden. Nun werden Sub-listen erstellt, f√ľr welche ein benutzerdefinierte Untergrenze (eine Zahl zw. 0.0 und 1.0) f√ľr alle m√∂glichen Kombinationen gegeben wird.

                              schade, ueberschrieben, morgen neu machen

                              Beispiel: Der String 'dresden' w√ľrde die Bigram-Liste ['dr','re','es','sd','de','en'] mit sechs Elementen ergeben. Es w√ľrde sortiert zu ['de','dr','en','es','re','sd'], und bei einer Untergrenze von 0.8 ergebe dies 6 * 0.8 = 4.8, gerundet 5, was bedeutet, dass alle Kombinationen der L√§nge 5 berrechnet werden. F√ľr das gegebene Beispiel

                              ['de','dr','en','es','re']

                              ['de','dr','en','es','sd']

                              ['de','dr','es','re','sd']

                              ['de','en','es','re','sd']

                              ['de','dr','en','re','sd']

                              ['dr','en','es','re','sd']

                              Damit wird die korrespondierende Datensatz-Nummer mit den Schl√ľsseln 'dedrenesre', 'dedrenessd', 'dedresresd', 'dedrenresd', 'drenesresd' und 'deenesresd' in die invertierten Index-Bl√∂cke eingef√ľgt.

                              Je geringer die Untergrenze, desto k√ľrzer die Sub-Liste, aber umso mehr Sub-Listen gibt es pro Feldwert, was zu mehr (kleineren) Bl√∂cken im invertierten Index f√ľhrt.

                              Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme T1 sowie die allgemeine Bigramm-L√§nge T2 identifiziert werden.

                              Daraus ergibt sich, wie beim Standard-Blocking, die Komplexität von O(n²/b) [tailor02], wobei b die Anzahl der zu vergleichenden Blöcke darstellt.

                              Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme sowie die allgemeine Bigramm-L√§nge identifiziert werden. Daraus ergibt sich, wie beim Standard-Blocking, die Komplexit√§t von [tailor02], wobei b die Anzahl der zu vergleichenden Bl√∂cke darstellt.

                              Diese besteht aus 2 Schritten, wobei der 1. Schritt einen Blockieralgorithmus in der Form darstellt, da√ü er √ľber eine billige Distanzmessung die Entit√§ten in n>= 1 sich √ľberlappende, sog. Canopy (engl. „Abdeckhaube“) einteilt. Dazu wird aus der Liste der Datens√§tze ein beliebiger Eintrag genommen und mit allen anderen Eintr√§gen der Liste verglichen (bspw. nach der Anzahl identischer Attribute). Alle Datens√§tze innerhalb der Distanz werden dabei in ein Canopy gegeben. Alle Datens√§tze innerhalb der Distanz werden von der Liste gel√∂scht. Dies wird wiederholt, bis die Liste leer ist.

                              SVG - Suchraumbestimmung - Canopy

                              Dadurch werden Nachteile des Grobblockings bzw. Sliding-Windows ausgeräumt, wie ein mögliches Paar außerhalb der Fenstergröße.

                              Die „Term-frequency-inverse data frequency“ (TF-IDF) Cosinus √Ąhnlichkeit ist eine billige Distanzmessungen, um sich √ľberlappende Datensatz-Cluster zu erstellen. Es basiert auf der Auftrittsh√§ufigkeit einzelner Terme und wird im Abschnitt [TDIDF] n√§her behandelt.

                              Im 2. Schritt werde daraufhin mit einer teureren Distanzmessung nur Punkt-Paare verglichen, welche sich im selben Canopy befinden.

                              Bei diesem Ansatz k√∂nnen 3 Parameter gesetzt werden: w√§hrend Stufe 1 der Loose-Grenzwert (T1) und der Tight-Grenzwert (T2) . Bei Verwendung des GAC (siehe unten), 3. Parameter der Stopp-Parameter, bei dessen erreichen keine weitere Iteration ausgef√ľhrt wird.

                              Die Berechnungskomplexit√§t kann bei Nutzung der invertierten Liste f√ľr Schritt 2 wie folgt dargestellt werden

                              w

                              Anzahl der Vergleichsdatensätze

                              V

                              die möglichen Werte der Attribute, |V| Anzahl der Canopies

                              n

                              Anzahl aller Entitäten/Datensätze

                              O(nw²V)

                              Loose und Tight sollten so gewählt werden, daß n gering und |V| möglichst groß ist, um den Umfang der Berechnung zu verringern. bei zu großen Werten können typographische Fehler nicht mehr erkannt werden.

                              Vergleichsmessungen, durchgef√ľhrt in [Kdd03]. Die Ergebniss-Anzahl bei Standard-Blocking k√∂nnen gro√üen Schwankungen unterliegen und nehmen mit zunehmenden Blockierschl√ľsseln rapide ab. Kleinere Bl√∂cke bedeuten dabei zwar weniger Vergleiche, schliessen jedoch ebenso mehr korrekte Paare aus.

                              Sorted-Neighbourhood-Methoden verhindern diese Extreme in der Performance des Standard Blockings und erlauben ein vorhersehbares Verhalten durch Erhöhung der Fenstergröße w. Durch größere Fenster erhöht sich die Paar-Vollständigkeit in den Ergebnissen, doch das Reduktionsverhältnis sinkt.

                              Mit gut gew√§hlten Parametern sind jedoch sowohl Bigramm- als auch Canopies-Clustering signifikant performanter. Bei Ersterem wird eine Bigram-Vergleichsanzahl von 3 - 4 empfohlen, der Schwellwert f√ľr Canopy sollte um 1.5 liegen.

                              . Komplexität korrekte Negative falsche Positive
                              Standard-Blocking n²/b ++ ++
                              Sliding Window n log n + wn + +
                              Bigramme n²/b - +
                              Canopy nw²/count(V) - +

                          Aus Gr√ľnden der Effizienz und Skalierbarkeit soll ein Vergleich aller Tupel in jeder Relation verhindert werden. Analog zu Schritt 2 aus dem Abschnitt "Strukturanalyse"  wird daher f√ľr jeden Datensatz der Suchraum zur Ableitung m√∂glicher Abbildungen begrenzt.

                          Da in der Menge A√óB im Allgemeinen viel mehr Nicht-Treffer als Treffer zu erwarten sind (u(γ)≫m(γ)), werden f√ľr einen Datensatz die Vergleichsdatens√§tze entfernt, welche auf keinen Fall zutreffen. Eine Vielzahl von Methoden haben als Aufgabe, die Rechenkosten der Namensfindung gering zu halten, indem eine erste Grobauswahl aus dem Gesamtdatenbestand isoliert wird. Sets von geordneten Paaren , auf denen der Fellegi-Sunter Verlinkungsalgorithmus Anwendung findet, sind daher mit „Blockierkriterien“ bzw. Sortierschl√ľssel belegt.

                          Man nehme als Beispiel ein Tupel-Set, in welchem eine Telefonnummer vorhanden ist. Diese Telefonnummer kann in Verbindung mit einigen wenigen Zeichen des Namens zur Bestimmung von Verlinkungen nutzen. Bei anderen Paaren mögen zusätzlich die Informationen zu Straßennamen und Stadtnamen zugrunde gelegt werden.

                          Standard-Blocking

                          Der traditionelle Blockier-Algorithmus gruppiert Datens√§tze, wenn diese den selben Inhalt in einer Blockiervariable besitzen, also bspw. den identischen Eintrag f√ľr Stadt und Nachname in einem Datensatz. Blockierkriterien m√ľssen dabei gut gew√§hlt werden, da bei zu allgemeinen Auswahlschl√ľsseln die Menge n√§her zu untersuchender Datens√§tze zu hoch ist (korrekte Negative), bei einer zu engen jedoch passende Datens√§tze ausgesperrt bleiben k√∂nnten (falsche Positive).

                          SVG - Suchraumbestimmung - Grobblocking

                          Ebenfalls muss die Fehler-Charakteristik des gew√§hlten Schl√ľssels bekannt und ein Fehlerauftritt minimal sein. Durch die Verwendung multipler Blockierschl√ľssel kann der Fehler in einem der Schl√ľssel abgemildert werden. Die Berechnungskomplexit√§t ist pro gew√§hlten Schl√ľssel, O(h(n)+n¬≤/b), wobei h(n) = n log n bei sortierter Blocking-Menge, h(n) = n bei blocking durch hashing. Die Ergebnissmengen sind allerdings nur schwer abzusch√§tzen.

                          Sorted-Neighbourhood / sliding window

                          Eine Weiterentwicklung stellt die Sorted-Neighbourhood- oder Fenster- Strategie ("windowing strategy") nach [HS95] dar. Sie sortiert einen Datenbestand nach dem Schl√ľssel ("Key")-Attribut mit dem gr√∂√üten Unterschied und vergleicht alle Records innerhalb eines fliessenden Fensters („sliding Window“) in der aussortierten Ordnung . Die Effektivit√§t dieses Ansatzes h√§ngt stark von der Qualit√§t des gew√§hlten Schl√ľssels ab.

                          Poor chosen keys will result in a poor quality merge

                          Die „Sorted-Neighbourhood“-Methode kann in 3 Phasen zusammengefasst werden:

                          1. Erstellen der Schl√ľssel: Errechne einen Schl√ľssel f√ľr jeden Datensatz in der Liste durch extrahieren relevanter Felder oder Feldbestandteile
                          2. Sortierung der Daten: Sortiere die Datens√§tze in der Datenliste unter Nutzung des Schl√ľssels aus Schritt 1
                          3. Vereine: Bewege ein Fenster mit konstanter Gr√∂√üe durch die sequentielle Liste der Datens√§tze und limitiere den Vergleich auf passende Werte auf solche innerhalb des Fensters. Falls die Fenstergr√∂√üe w Datens√§tze umfasst, so wird jeder neuer Datensatz mit den vorhergehenden w-1 S√§tzen verglichen, um „passende Datens√§tze“ zu finden. Der erste Datensatz im Fenster slided dabei aus dem Fensterbereich.
                          SVG - Suchraumbestimmung - Sliding Window

                          Bei sehr gro√üen Datenmengen empfiehlt sich ein vorheriges Clustern des Datenbestandes. Dabei wird der Datenbestand in Sequenzen durchsucht, wobei ein n-attributiger Schl√ľssel (Bsp. Nachname+1.Buchstabe des Vornamens) extrahiert und in den n-dimensionalen Clusterraum abgebildet wird.

                          Da auch dieses gew√§hlte Attribut einen Fehler besitzen kann, ist ein einzelnes Schl√ľsselattribut zu wenig. Um demnach Fehler im Hauptschl√ľssel auszuschlie√üen, schl√§gt [HS95] folgende Methoden vor:

                          1. Durch die Vergrößerung des sliding-windows werden mehr Datensätze mit eingeschlossen.
                          2. ein mehrmaliges Ausf√ľhren mit unterschiedlichen Schl√ľsseln und relativ kleinem Fenster gibt, nach einzelnem Abgleich der Ergebniss-Gruppen und transitivem Schlie√üen (nur bei geringer Fenstergr√∂√üe empfehlenswert) die besseren Ergebnisse.

                          Als Grenzwerte sind hier die Schl√ľsselanzahl j sowie die Fenstergr√∂√üe w anzugeben. Damit errechnet sich f√ľr n Datens√§tze eine Komplexit√§t von O(i=0j(nlogn+wn)) , wobei O(nlogn) f√ľr die Sortierung ben√∂tigt wird.

                          Fuzzy Blocking / Bigramm-Indexing

                          Diese Methode basiert auf Bigramme (in [SprachSynth06] auch Diphone oder Halblaute genannt). Die Grundidee dabei besteht darin, dass nach der Indexerstellung die Werte der Blockiervariablen in eine Liste von Bigramme (Diphone, Halblaute) konvertiert werden, welche alphabetisch sortiert und von Duplikaten bereinigt werden. Nun werden Sub-listen erstellt, f√ľr welche ein benutzerdefinierte Untergrenze (eine Zahl zw. 0.0 und 1.0) f√ľr alle m√∂glichen Kombinationen gegeben wird.

                          schade, ueberschrieben, morgen neu machen

                          Beispiel: Der String 'dresden' w√ľrde die Bigram-Liste ['dr','re','es','sd','de','en'] mit sechs Elementen ergeben. Es w√ľrde sortiert zu ['de','dr','en','es','re','sd'], und bei einer Untergrenze von 0.8 ergebe dies 6 * 0.8 = 4.8, gerundet 5, was bedeutet, dass alle Kombinationen der L√§nge 5 berrechnet werden. F√ľr das gegebene Beispiel

                          ['de','dr','en','es','re']

                          ['de','dr','en','es','sd']

                          ['de','dr','es','re','sd']

                          ['de','en','es','re','sd']

                          ['de','dr','en','re','sd']

                          ['dr','en','es','re','sd']

                          Damit wird die korrespondierende Datensatz-Nummer mit den Schl√ľsseln 'dedrenesre', 'dedrenessd', 'dedresresd', 'dedrenresd', 'drenesresd' und 'deenesresd' in die invertierten Index-Bl√∂cke eingef√ľgt.

                          Je geringer die Untergrenze, desto k√ľrzer die Sub-Liste, aber umso mehr Sub-Listen gibt es pro Feldwert, was zu mehr (kleineren) Bl√∂cken im invertierten Index f√ľhrt.

                          Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme T1 sowie die allgemeine Bigramm-L√§nge T2 identifiziert werden.

                          Daraus ergibt sich, wie beim Standard-Blocking, die Komplexität von O(n²/b) [tailor02], wobei b die Anzahl der zu vergleichenden Blöcke darstellt.

                          Canopy-Methode

                          Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme sowie die allgemeine Bigramm-L√§nge identifiziert werden. Daraus ergibt sich, wie beim Standard-Blocking, die Komplexit√§t von [tailor02], wobei b die Anzahl der zu vergleichenden Bl√∂cke darstellt.

                          Diese besteht aus 2 Schritten, wobei der 1. Schritt einen Blockieralgorithmus in der Form darstellt, da√ü er √ľber eine billige Distanzmessung die Entit√§ten in n>= 1 sich √ľberlappende, sog. Canopy (engl. „Abdeckhaube“) einteilt. Dazu wird aus der Liste der Datens√§tze ein beliebiger Eintrag genommen und mit allen anderen Eintr√§gen der Liste verglichen (bspw. nach der Anzahl identischer Attribute). Alle Datens√§tze innerhalb der Distanz werden dabei in ein Canopy gegeben. Alle Datens√§tze innerhalb der Distanz werden von der Liste gel√∂scht. Dies wird wiederholt, bis die Liste leer ist.

                          SVG - Suchraumbestimmung - Canopy

                          Dadurch werden Nachteile des Grobblockings bzw. Sliding-Windows ausgeräumt, wie ein mögliches Paar außerhalb der Fenstergröße.

                          Die „Term-frequency-inverse data frequency“ (TF-IDF) Cosinus √Ąhnlichkeit ist eine billige Distanzmessungen, um sich √ľberlappende Datensatz-Cluster zu erstellen. Es basiert auf der Auftrittsh√§ufigkeit einzelner Terme und wird im Abschnitt [TDIDF] n√§her behandelt.

                          Im 2. Schritt werde daraufhin mit einer teureren Distanzmessung nur Punkt-Paare verglichen, welche sich im selben Canopy befinden.

                          Bei diesem Ansatz k√∂nnen 3 Parameter gesetzt werden: w√§hrend Stufe 1 der Loose-Grenzwert (T1) und der Tight-Grenzwert (T2) . Bei Verwendung des GAC (siehe unten), 3. Parameter der Stopp-Parameter, bei dessen erreichen keine weitere Iteration ausgef√ľhrt wird.

                          Die Berechnungskomplexit√§t kann bei Nutzung der invertierten Liste f√ľr Schritt 2 wie folgt dargestellt werden

                          w

                          Anzahl der Vergleichsdatensätze

                          V

                          die möglichen Werte der Attribute, |V| Anzahl der Canopies

                          n

                          Anzahl aller Entitäten/Datensätze

                          O(nw²V)

                          Loose und Tight sollten so gewählt werden, daß n gering und |V| möglichst groß ist, um den Umfang der Berechnung zu verringern. bei zu großen Werten können typographische Fehler nicht mehr erkannt werden.

                          Zusammenfassung

                          Vergleichsmessungen, durchgef√ľhrt in [Kdd03]. Die Ergebniss-Anzahl bei Standard-Blocking k√∂nnen gro√üen Schwankungen unterliegen und nehmen mit zunehmenden Blockierschl√ľsseln rapide ab. Kleinere Bl√∂cke bedeuten dabei zwar weniger Vergleiche, schliessen jedoch ebenso mehr korrekte Paare aus.

                          Sorted-Neighbourhood-Methoden verhindern diese Extreme in der Performance des Standard Blockings und erlauben ein vorhersehbares Verhalten durch Erhöhung der Fenstergröße w. Durch größere Fenster erhöht sich die Paar-Vollständigkeit in den Ergebnissen, doch das Reduktionsverhältnis sinkt.

                          Mit gut gew√§hlten Parametern sind jedoch sowohl Bigramm- als auch Canopies-Clustering signifikant performanter. Bei Ersterem wird eine Bigram-Vergleichsanzahl von 3 - 4 empfohlen, der Schwellwert f√ľr Canopy sollte um 1.5 liegen.

                          . Komplexität korrekte Negative falsche Positive
                          Standard-Blocking n²/b ++ ++
                          Sliding Window n log n + wn + +
                          Bigramme n²/b - +
                          Canopy nw²/count(V) - +

                      Aus Gr√ľnden der Effizienz und Skalierbarkeit soll ein Vergleich aller Tupel in jeder Relation verhindert werden. Analog zu Schritt 2 aus dem Abschnitt "Strukturanalyse"  wird daher f√ľr jeden Datensatz der Suchraum zur Ableitung m√∂glicher Abbildungen begrenzt.

                      Da in der Menge A√óB im Allgemeinen viel mehr Nicht-Treffer als Treffer zu erwarten sind (u(γ)≫m(γ)), werden f√ľr einen Datensatz die Vergleichsdatens√§tze entfernt, welche auf keinen Fall zutreffen. Eine Vielzahl von Methoden haben als Aufgabe, die Rechenkosten der Namensfindung gering zu halten, indem eine erste Grobauswahl aus dem Gesamtdatenbestand isoliert wird. Sets von geordneten Paaren , auf denen der Fellegi-Sunter Verlinkungsalgorithmus Anwendung findet, sind daher mit „Blockierkriterien“ bzw. Sortierschl√ľssel belegt.

                      Man nehme als Beispiel ein Tupel-Set, in welchem eine Telefonnummer vorhanden ist. Diese Telefonnummer kann in Verbindung mit einigen wenigen Zeichen des Namens zur Bestimmung von Verlinkungen nutzen. Bei anderen Paaren mögen zusätzlich die Informationen zu Straßennamen und Stadtnamen zugrunde gelegt werden.

                      Standard-Blocking

                      Der traditionelle Blockier-Algorithmus gruppiert Datens√§tze, wenn diese den selben Inhalt in einer Blockiervariable besitzen, also bspw. den identischen Eintrag f√ľr Stadt und Nachname in einem Datensatz. Blockierkriterien m√ľssen dabei gut gew√§hlt werden, da bei zu allgemeinen Auswahlschl√ľsseln die Menge n√§her zu untersuchender Datens√§tze zu hoch ist (korrekte Negative), bei einer zu engen jedoch passende Datens√§tze ausgesperrt bleiben k√∂nnten (falsche Positive).

                      SVG - Suchraumbestimmung - Grobblocking

                      Ebenfalls muss die Fehler-Charakteristik des gew√§hlten Schl√ľssels bekannt und ein Fehlerauftritt minimal sein. Durch die Verwendung multipler Blockierschl√ľssel kann der Fehler in einem der Schl√ľssel abgemildert werden. Die Berechnungskomplexit√§t ist pro gew√§hlten Schl√ľssel, O(h(n)+n¬≤/b), wobei h(n) = n log n bei sortierter Blocking-Menge, h(n) = n bei blocking durch hashing. Die Ergebnissmengen sind allerdings nur schwer abzusch√§tzen.

                      Sorted-Neighbourhood / sliding window

                      Eine Weiterentwicklung stellt die Sorted-Neighbourhood- oder Fenster- Strategie ("windowing strategy") nach [HS95] dar. Sie sortiert einen Datenbestand nach dem Schl√ľssel ("Key")-Attribut mit dem gr√∂√üten Unterschied und vergleicht alle Records innerhalb eines fliessenden Fensters („sliding Window“) in der aussortierten Ordnung . Die Effektivit√§t dieses Ansatzes h√§ngt stark von der Qualit√§t des gew√§hlten Schl√ľssels ab.

                      Poor chosen keys will result in a poor quality merge

                      Die „Sorted-Neighbourhood“-Methode kann in 3 Phasen zusammengefasst werden:

                      1. Erstellen der Schl√ľssel: Errechne einen Schl√ľssel f√ľr jeden Datensatz in der Liste durch extrahieren relevanter Felder oder Feldbestandteile
                      2. Sortierung der Daten: Sortiere die Datens√§tze in der Datenliste unter Nutzung des Schl√ľssels aus Schritt 1
                      3. Vereine: Bewege ein Fenster mit konstanter Gr√∂√üe durch die sequentielle Liste der Datens√§tze und limitiere den Vergleich auf passende Werte auf solche innerhalb des Fensters. Falls die Fenstergr√∂√üe w Datens√§tze umfasst, so wird jeder neuer Datensatz mit den vorhergehenden w-1 S√§tzen verglichen, um „passende Datens√§tze“ zu finden. Der erste Datensatz im Fenster slided dabei aus dem Fensterbereich.
                      SVG - Suchraumbestimmung - Sliding Window

                      Bei sehr gro√üen Datenmengen empfiehlt sich ein vorheriges Clustern des Datenbestandes. Dabei wird der Datenbestand in Sequenzen durchsucht, wobei ein n-attributiger Schl√ľssel (Bsp. Nachname+1.Buchstabe des Vornamens) extrahiert und in den n-dimensionalen Clusterraum abgebildet wird.

                      Da auch dieses gew√§hlte Attribut einen Fehler besitzen kann, ist ein einzelnes Schl√ľsselattribut zu wenig. Um demnach Fehler im Hauptschl√ľssel auszuschlie√üen, schl√§gt [HS95] folgende Methoden vor:

                      1. Durch die Vergrößerung des sliding-windows werden mehr Datensätze mit eingeschlossen.
                      2. ein mehrmaliges Ausf√ľhren mit unterschiedlichen Schl√ľsseln und relativ kleinem Fenster gibt, nach einzelnem Abgleich der Ergebniss-Gruppen und transitivem Schlie√üen (nur bei geringer Fenstergr√∂√üe empfehlenswert) die besseren Ergebnisse.

                      Als Grenzwerte sind hier die Schl√ľsselanzahl j sowie die Fenstergr√∂√üe w anzugeben. Damit errechnet sich f√ľr n Datens√§tze eine Komplexit√§t von O(i=0j(nlogn+wn)) , wobei O(nlogn) f√ľr die Sortierung ben√∂tigt wird.

                      Fuzzy Blocking / Bigramm-Indexing

                      Diese Methode basiert auf Bigramme (in [SprachSynth06] auch Diphone oder Halblaute genannt). Die Grundidee dabei besteht darin, dass nach der Indexerstellung die Werte der Blockiervariablen in eine Liste von Bigramme (Diphone, Halblaute) konvertiert werden, welche alphabetisch sortiert und von Duplikaten bereinigt werden. Nun werden Sub-listen erstellt, f√ľr welche ein benutzerdefinierte Untergrenze (eine Zahl zw. 0.0 und 1.0) f√ľr alle m√∂glichen Kombinationen gegeben wird.

                      schade, ueberschrieben, morgen neu machen

                      Beispiel: Der String 'dresden' w√ľrde die Bigram-Liste ['dr','re','es','sd','de','en'] mit sechs Elementen ergeben. Es w√ľrde sortiert zu ['de','dr','en','es','re','sd'], und bei einer Untergrenze von 0.8 ergebe dies 6 * 0.8 = 4.8, gerundet 5, was bedeutet, dass alle Kombinationen der L√§nge 5 berrechnet werden. F√ľr das gegebene Beispiel

                      ['de','dr','en','es','re']

                      ['de','dr','en','es','sd']

                      ['de','dr','es','re','sd']

                      ['de','en','es','re','sd']

                      ['de','dr','en','re','sd']

                      ['dr','en','es','re','sd']

                      Damit wird die korrespondierende Datensatz-Nummer mit den Schl√ľsseln 'dedrenesre', 'dedrenessd', 'dedresresd', 'dedrenresd', 'drenesresd' und 'deenesresd' in die invertierten Index-Bl√∂cke eingef√ľgt.

                      Je geringer die Untergrenze, desto k√ľrzer die Sub-Liste, aber umso mehr Sub-Listen gibt es pro Feldwert, was zu mehr (kleineren) Bl√∂cken im invertierten Index f√ľhrt.

                      Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme T1 sowie die allgemeine Bigramm-L√§nge T2 identifiziert werden.

                      Daraus ergibt sich, wie beim Standard-Blocking, die Komplexität von O(n²/b) [tailor02], wobei b die Anzahl der zu vergleichenden Blöcke darstellt.

                      Canopy-Methode

                      Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme sowie die allgemeine Bigramm-L√§nge identifiziert werden. Daraus ergibt sich, wie beim Standard-Blocking, die Komplexit√§t von [tailor02], wobei b die Anzahl der zu vergleichenden Bl√∂cke darstellt.

                      Diese besteht aus 2 Schritten, wobei der 1. Schritt einen Blockieralgorithmus in der Form darstellt, da√ü er √ľber eine billige Distanzmessung die Entit√§ten in n>= 1 sich √ľberlappende, sog. Canopy (engl. „Abdeckhaube“) einteilt. Dazu wird aus der Liste der Datens√§tze ein beliebiger Eintrag genommen und mit allen anderen Eintr√§gen der Liste verglichen (bspw. nach der Anzahl identischer Attribute). Alle Datens√§tze innerhalb der Distanz werden dabei in ein Canopy gegeben. Alle Datens√§tze innerhalb der Distanz werden von der Liste gel√∂scht. Dies wird wiederholt, bis die Liste leer ist.

                      SVG - Suchraumbestimmung - Canopy

                      Dadurch werden Nachteile des Grobblockings bzw. Sliding-Windows ausgeräumt, wie ein mögliches Paar außerhalb der Fenstergröße.

                      Die „Term-frequency-inverse data frequency“ (TF-IDF) Cosinus √Ąhnlichkeit ist eine billige Distanzmessungen, um sich √ľberlappende Datensatz-Cluster zu erstellen. Es basiert auf der Auftrittsh√§ufigkeit einzelner Terme und wird im Abschnitt [TDIDF] n√§her behandelt.

                      Im 2. Schritt werde daraufhin mit einer teureren Distanzmessung nur Punkt-Paare verglichen, welche sich im selben Canopy befinden.

                      Bei diesem Ansatz k√∂nnen 3 Parameter gesetzt werden: w√§hrend Stufe 1 der Loose-Grenzwert (T1) und der Tight-Grenzwert (T2) . Bei Verwendung des GAC (siehe unten), 3. Parameter der Stopp-Parameter, bei dessen erreichen keine weitere Iteration ausgef√ľhrt wird.

                      Die Berechnungskomplexit√§t kann bei Nutzung der invertierten Liste f√ľr Schritt 2 wie folgt dargestellt werden

                      w

                      Anzahl der Vergleichsdatensätze

                      V

                      die möglichen Werte der Attribute, |V| Anzahl der Canopies

                      n

                      Anzahl aller Entitäten/Datensätze

                      O(nw²V)

                      Loose und Tight sollten so gewählt werden, daß n gering und |V| möglichst groß ist, um den Umfang der Berechnung zu verringern. bei zu großen Werten können typographische Fehler nicht mehr erkannt werden.

                      Zusammenfassung

                      Vergleichsmessungen, durchgef√ľhrt in [Kdd03]. Die Ergebniss-Anzahl bei Standard-Blocking k√∂nnen gro√üen Schwankungen unterliegen und nehmen mit zunehmenden Blockierschl√ľsseln rapide ab. Kleinere Bl√∂cke bedeuten dabei zwar weniger Vergleiche, schliessen jedoch ebenso mehr korrekte Paare aus.

                      Sorted-Neighbourhood-Methoden verhindern diese Extreme in der Performance des Standard Blockings und erlauben ein vorhersehbares Verhalten durch Erhöhung der Fenstergröße w. Durch größere Fenster erhöht sich die Paar-Vollständigkeit in den Ergebnissen, doch das Reduktionsverhältnis sinkt.

                      Mit gut gew√§hlten Parametern sind jedoch sowohl Bigramm- als auch Canopies-Clustering signifikant performanter. Bei Ersterem wird eine Bigram-Vergleichsanzahl von 3 - 4 empfohlen, der Schwellwert f√ľr Canopy sollte um 1.5 liegen.

                      . Komplexität korrekte Negative falsche Positive
                      Standard-Blocking n²/b ++ ++
                      Sliding Window n log n + wn + +
                      Bigramme n²/b - +
                      Canopy nw²/count(V) - +

                  Aus Gr√ľnden der Effizienz und Skalierbarkeit soll ein Vergleich aller Tupel in jeder Relation verhindert werden. Analog zu Schritt 2 aus dem Abschnitt "Strukturanalyse"  wird daher f√ľr jeden Datensatz der Suchraum zur Ableitung m√∂glicher Abbildungen begrenzt.

                  Da in der Menge A√óB im Allgemeinen viel mehr Nicht-Treffer als Treffer zu erwarten sind (u(γ)≫m(γ)), werden f√ľr einen Datensatz die Vergleichsdatens√§tze entfernt, welche auf keinen Fall zutreffen. Eine Vielzahl von Methoden haben als Aufgabe, die Rechenkosten der Namensfindung gering zu halten, indem eine erste Grobauswahl aus dem Gesamtdatenbestand isoliert wird. Sets von geordneten Paaren , auf denen der Fellegi-Sunter Verlinkungsalgorithmus Anwendung findet, sind daher mit „Blockierkriterien“ bzw. Sortierschl√ľssel belegt.

                  Man nehme als Beispiel ein Tupel-Set, in welchem eine Telefonnummer vorhanden ist. Diese Telefonnummer kann in Verbindung mit einigen wenigen Zeichen des Namens zur Bestimmung von Verlinkungen nutzen. Bei anderen Paaren mögen zusätzlich die Informationen zu Straßennamen und Stadtnamen zugrunde gelegt werden.

                  Standard-Blocking

                  Der traditionelle Blockier-Algorithmus gruppiert Datens√§tze, wenn diese den selben Inhalt in einer Blockiervariable besitzen, also bspw. den identischen Eintrag f√ľr Stadt und Nachname in einem Datensatz. Blockierkriterien m√ľssen dabei gut gew√§hlt werden, da bei zu allgemeinen Auswahlschl√ľsseln die Menge n√§her zu untersuchender Datens√§tze zu hoch ist (korrekte Negative), bei einer zu engen jedoch passende Datens√§tze ausgesperrt bleiben k√∂nnten (falsche Positive).

                  SVG - Suchraumbestimmung - Grobblocking

                  Ebenfalls muss die Fehler-Charakteristik des gew√§hlten Schl√ľssels bekannt und ein Fehlerauftritt minimal sein. Durch die Verwendung multipler Blockierschl√ľssel kann der Fehler in einem der Schl√ľssel abgemildert werden. Die Berechnungskomplexit√§t ist pro gew√§hlten Schl√ľssel, O(h(n)+n¬≤/b), wobei h(n) = n log n bei sortierter Blocking-Menge, h(n) = n bei blocking durch hashing. Die Ergebnissmengen sind allerdings nur schwer abzusch√§tzen.

                  Sorted-Neighbourhood / sliding window

                  Eine Weiterentwicklung stellt die Sorted-Neighbourhood- oder Fenster- Strategie ("windowing strategy") nach [HS95] dar. Sie sortiert einen Datenbestand nach dem Schl√ľssel ("Key")-Attribut mit dem gr√∂√üten Unterschied und vergleicht alle Records innerhalb eines fliessenden Fensters („sliding Window“) in der aussortierten Ordnung . Die Effektivit√§t dieses Ansatzes h√§ngt stark von der Qualit√§t des gew√§hlten Schl√ľssels ab.

                  Poor chosen keys will result in a poor quality merge

                  Die „Sorted-Neighbourhood“-Methode kann in 3 Phasen zusammengefasst werden:

                  1. Erstellen der Schl√ľssel: Errechne einen Schl√ľssel f√ľr jeden Datensatz in der Liste durch extrahieren relevanter Felder oder Feldbestandteile
                  2. Sortierung der Daten: Sortiere die Datens√§tze in der Datenliste unter Nutzung des Schl√ľssels aus Schritt 1
                  3. Vereine: Bewege ein Fenster mit konstanter Gr√∂√üe durch die sequentielle Liste der Datens√§tze und limitiere den Vergleich auf passende Werte auf solche innerhalb des Fensters. Falls die Fenstergr√∂√üe w Datens√§tze umfasst, so wird jeder neuer Datensatz mit den vorhergehenden w-1 S√§tzen verglichen, um „passende Datens√§tze“ zu finden. Der erste Datensatz im Fenster slided dabei aus dem Fensterbereich.
                  SVG - Suchraumbestimmung - Sliding Window

                  Bei sehr gro√üen Datenmengen empfiehlt sich ein vorheriges Clustern des Datenbestandes. Dabei wird der Datenbestand in Sequenzen durchsucht, wobei ein n-attributiger Schl√ľssel (Bsp. Nachname+1.Buchstabe des Vornamens) extrahiert und in den n-dimensionalen Clusterraum abgebildet wird.

                  Da auch dieses gew√§hlte Attribut einen Fehler besitzen kann, ist ein einzelnes Schl√ľsselattribut zu wenig. Um demnach Fehler im Hauptschl√ľssel auszuschlie√üen, schl√§gt [HS95] folgende Methoden vor:

                  1. Durch die Vergrößerung des sliding-windows werden mehr Datensätze mit eingeschlossen.
                  2. ein mehrmaliges Ausf√ľhren mit unterschiedlichen Schl√ľsseln und relativ kleinem Fenster gibt, nach einzelnem Abgleich der Ergebniss-Gruppen und transitivem Schlie√üen (nur bei geringer Fenstergr√∂√üe empfehlenswert) die besseren Ergebnisse.

                  Als Grenzwerte sind hier die Schl√ľsselanzahl j sowie die Fenstergr√∂√üe w anzugeben. Damit errechnet sich f√ľr n Datens√§tze eine Komplexit√§t von O(i=0j(nlogn+wn)) , wobei O(nlogn) f√ľr die Sortierung ben√∂tigt wird.

                  Fuzzy Blocking / Bigramm-Indexing

                  Diese Methode basiert auf Bigramme (in [SprachSynth06] auch Diphone oder Halblaute genannt). Die Grundidee dabei besteht darin, dass nach der Indexerstellung die Werte der Blockiervariablen in eine Liste von Bigramme (Diphone, Halblaute) konvertiert werden, welche alphabetisch sortiert und von Duplikaten bereinigt werden. Nun werden Sub-listen erstellt, f√ľr welche ein benutzerdefinierte Untergrenze (eine Zahl zw. 0.0 und 1.0) f√ľr alle m√∂glichen Kombinationen gegeben wird.

                  schade, ueberschrieben, morgen neu machen

                  Beispiel: Der String 'dresden' w√ľrde die Bigram-Liste ['dr','re','es','sd','de','en'] mit sechs Elementen ergeben. Es w√ľrde sortiert zu ['de','dr','en','es','re','sd'], und bei einer Untergrenze von 0.8 ergebe dies 6 * 0.8 = 4.8, gerundet 5, was bedeutet, dass alle Kombinationen der L√§nge 5 berrechnet werden. F√ľr das gegebene Beispiel

                  ['de','dr','en','es','re']

                  ['de','dr','en','es','sd']

                  ['de','dr','es','re','sd']

                  ['de','en','es','re','sd']

                  ['de','dr','en','re','sd']

                  ['dr','en','es','re','sd']

                  Damit wird die korrespondierende Datensatz-Nummer mit den Schl√ľsseln 'dedrenesre', 'dedrenessd', 'dedresresd', 'dedrenresd', 'drenesresd' und 'deenesresd' in die invertierten Index-Bl√∂cke eingef√ľgt.

                  Je geringer die Untergrenze, desto k√ľrzer die Sub-Liste, aber umso mehr Sub-Listen gibt es pro Feldwert, was zu mehr (kleineren) Bl√∂cken im invertierten Index f√ľhrt.

                  Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme T1 sowie die allgemeine Bigramm-L√§nge T2 identifiziert werden.

                  Daraus ergibt sich, wie beim Standard-Blocking, die Komplexität von O(n²/b) [tailor02], wobei b die Anzahl der zu vergleichenden Blöcke darstellt.

                  Canopy-Methode

                  Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme sowie die allgemeine Bigramm-L√§nge identifiziert werden. Daraus ergibt sich, wie beim Standard-Blocking, die Komplexit√§t von [tailor02], wobei b die Anzahl der zu vergleichenden Bl√∂cke darstellt.

                  Diese besteht aus 2 Schritten, wobei der 1. Schritt einen Blockieralgorithmus in der Form darstellt, da√ü er √ľber eine billige Distanzmessung die Entit√§ten in n>= 1 sich √ľberlappende, sog. Canopy (engl. „Abdeckhaube“) einteilt. Dazu wird aus der Liste der Datens√§tze ein beliebiger Eintrag genommen und mit allen anderen Eintr√§gen der Liste verglichen (bspw. nach der Anzahl identischer Attribute). Alle Datens√§tze innerhalb der Distanz werden dabei in ein Canopy gegeben. Alle Datens√§tze innerhalb der Distanz werden von der Liste gel√∂scht. Dies wird wiederholt, bis die Liste leer ist.

                  SVG - Suchraumbestimmung - Canopy

                  Dadurch werden Nachteile des Grobblockings bzw. Sliding-Windows ausgeräumt, wie ein mögliches Paar außerhalb der Fenstergröße.

                  Die „Term-frequency-inverse data frequency“ (TF-IDF) Cosinus √Ąhnlichkeit ist eine billige Distanzmessungen, um sich √ľberlappende Datensatz-Cluster zu erstellen. Es basiert auf der Auftrittsh√§ufigkeit einzelner Terme und wird im Abschnitt [TDIDF] n√§her behandelt.

                  Im 2. Schritt werde daraufhin mit einer teureren Distanzmessung nur Punkt-Paare verglichen, welche sich im selben Canopy befinden.

                  Bei diesem Ansatz k√∂nnen 3 Parameter gesetzt werden: w√§hrend Stufe 1 der Loose-Grenzwert (T1) und der Tight-Grenzwert (T2) . Bei Verwendung des GAC (siehe unten), 3. Parameter der Stopp-Parameter, bei dessen erreichen keine weitere Iteration ausgef√ľhrt wird.

                  Die Berechnungskomplexit√§t kann bei Nutzung der invertierten Liste f√ľr Schritt 2 wie folgt dargestellt werden

                  w

                  Anzahl der Vergleichsdatensätze

                  V

                  die möglichen Werte der Attribute, |V| Anzahl der Canopies

                  n

                  Anzahl aller Entitäten/Datensätze

                  O(nw²V)

                  Loose und Tight sollten so gewählt werden, daß n gering und |V| möglichst groß ist, um den Umfang der Berechnung zu verringern. bei zu großen Werten können typographische Fehler nicht mehr erkannt werden.

                  Zusammenfassung

                  Vergleichsmessungen, durchgef√ľhrt in [Kdd03]. Die Ergebniss-Anzahl bei Standard-Blocking k√∂nnen gro√üen Schwankungen unterliegen und nehmen mit zunehmenden Blockierschl√ľsseln rapide ab. Kleinere Bl√∂cke bedeuten dabei zwar weniger Vergleiche, schliessen jedoch ebenso mehr korrekte Paare aus.

                  Sorted-Neighbourhood-Methoden verhindern diese Extreme in der Performance des Standard Blockings und erlauben ein vorhersehbares Verhalten durch Erhöhung der Fenstergröße w. Durch größere Fenster erhöht sich die Paar-Vollständigkeit in den Ergebnissen, doch das Reduktionsverhältnis sinkt.

                  Mit gut gew√§hlten Parametern sind jedoch sowohl Bigramm- als auch Canopies-Clustering signifikant performanter. Bei Ersterem wird eine Bigram-Vergleichsanzahl von 3 - 4 empfohlen, der Schwellwert f√ľr Canopy sollte um 1.5 liegen.

                  . Komplexität korrekte Negative falsche Positive
                  Standard-Blocking n²/b ++ ++
                  Sliding Window n log n + wn + +
                  Bigramme n²/b - +
                  Canopy nw²/count(V) - +

              Aus Gr√ľnden der Effizienz und Skalierbarkeit soll ein Vergleich aller Tupel in jeder Relation verhindert werden. Analog zu Schritt 2 aus dem Abschnitt "Strukturanalyse"  wird daher f√ľr jeden Datensatz der Suchraum zur Ableitung m√∂glicher Abbildungen begrenzt.

              Da in der Menge A√óB im Allgemeinen viel mehr Nicht-Treffer als Treffer zu erwarten sind (u(γ)≫m(γ)), werden f√ľr einen Datensatz die Vergleichsdatens√§tze entfernt, welche auf keinen Fall zutreffen. Eine Vielzahl von Methoden haben als Aufgabe, die Rechenkosten der Namensfindung gering zu halten, indem eine erste Grobauswahl aus dem Gesamtdatenbestand isoliert wird. Sets von geordneten Paaren , auf denen der Fellegi-Sunter Verlinkungsalgorithmus Anwendung findet, sind daher mit „Blockierkriterien“ bzw. Sortierschl√ľssel belegt.

              Man nehme als Beispiel ein Tupel-Set, in welchem eine Telefonnummer vorhanden ist. Diese Telefonnummer kann in Verbindung mit einigen wenigen Zeichen des Namens zur Bestimmung von Verlinkungen nutzen. Bei anderen Paaren mögen zusätzlich die Informationen zu Straßennamen und Stadtnamen zugrunde gelegt werden.

              Standard-Blocking

              Der traditionelle Blockier-Algorithmus gruppiert Datens√§tze, wenn diese den selben Inhalt in einer Blockiervariable besitzen, also bspw. den identischen Eintrag f√ľr Stadt und Nachname in einem Datensatz. Blockierkriterien m√ľssen dabei gut gew√§hlt werden, da bei zu allgemeinen Auswahlschl√ľsseln die Menge n√§her zu untersuchender Datens√§tze zu hoch ist (korrekte Negative), bei einer zu engen jedoch passende Datens√§tze ausgesperrt bleiben k√∂nnten (falsche Positive).

              SVG - Suchraumbestimmung - Grobblocking

              Ebenfalls muss die Fehler-Charakteristik des gew√§hlten Schl√ľssels bekannt und ein Fehlerauftritt minimal sein. Durch die Verwendung multipler Blockierschl√ľssel kann der Fehler in einem der Schl√ľssel abgemildert werden. Die Berechnungskomplexit√§t ist pro gew√§hlten Schl√ľssel, O(h(n)+n¬≤/b), wobei h(n) = n log n bei sortierter Blocking-Menge, h(n) = n bei blocking durch hashing. Die Ergebnissmengen sind allerdings nur schwer abzusch√§tzen.

              Sorted-Neighbourhood / sliding window

              Eine Weiterentwicklung stellt die Sorted-Neighbourhood- oder Fenster- Strategie ("windowing strategy") nach [HS95] dar. Sie sortiert einen Datenbestand nach dem Schl√ľssel ("Key")-Attribut mit dem gr√∂√üten Unterschied und vergleicht alle Records innerhalb eines fliessenden Fensters („sliding Window“) in der aussortierten Ordnung . Die Effektivit√§t dieses Ansatzes h√§ngt stark von der Qualit√§t des gew√§hlten Schl√ľssels ab.

              Poor chosen keys will result in a poor quality merge

              Die „Sorted-Neighbourhood“-Methode kann in 3 Phasen zusammengefasst werden:

              1. Erstellen der Schl√ľssel: Errechne einen Schl√ľssel f√ľr jeden Datensatz in der Liste durch extrahieren relevanter Felder oder Feldbestandteile
              2. Sortierung der Daten: Sortiere die Datens√§tze in der Datenliste unter Nutzung des Schl√ľssels aus Schritt 1
              3. Vereine: Bewege ein Fenster mit konstanter Gr√∂√üe durch die sequentielle Liste der Datens√§tze und limitiere den Vergleich auf passende Werte auf solche innerhalb des Fensters. Falls die Fenstergr√∂√üe w Datens√§tze umfasst, so wird jeder neuer Datensatz mit den vorhergehenden w-1 S√§tzen verglichen, um „passende Datens√§tze“ zu finden. Der erste Datensatz im Fenster slided dabei aus dem Fensterbereich.
              SVG - Suchraumbestimmung - Sliding Window

              Bei sehr gro√üen Datenmengen empfiehlt sich ein vorheriges Clustern des Datenbestandes. Dabei wird der Datenbestand in Sequenzen durchsucht, wobei ein n-attributiger Schl√ľssel (Bsp. Nachname+1.Buchstabe des Vornamens) extrahiert und in den n-dimensionalen Clusterraum abgebildet wird.

              Da auch dieses gew√§hlte Attribut einen Fehler besitzen kann, ist ein einzelnes Schl√ľsselattribut zu wenig. Um demnach Fehler im Hauptschl√ľssel auszuschlie√üen, schl√§gt [HS95] folgende Methoden vor:

              1. Durch die Vergrößerung des sliding-windows werden mehr Datensätze mit eingeschlossen.
              2. ein mehrmaliges Ausf√ľhren mit unterschiedlichen Schl√ľsseln und relativ kleinem Fenster gibt, nach einzelnem Abgleich der Ergebniss-Gruppen und transitivem Schlie√üen (nur bei geringer Fenstergr√∂√üe empfehlenswert) die besseren Ergebnisse.

              Als Grenzwerte sind hier die Schl√ľsselanzahl j sowie die Fenstergr√∂√üe w anzugeben. Damit errechnet sich f√ľr n Datens√§tze eine Komplexit√§t von O(i=0j(nlogn+wn)) , wobei O(nlogn) f√ľr die Sortierung ben√∂tigt wird.

              Fuzzy Blocking / Bigramm-Indexing

              Diese Methode basiert auf Bigramme (in [SprachSynth06] auch Diphone oder Halblaute genannt). Die Grundidee dabei besteht darin, dass nach der Indexerstellung die Werte der Blockiervariablen in eine Liste von Bigramme (Diphone, Halblaute) konvertiert werden, welche alphabetisch sortiert und von Duplikaten bereinigt werden. Nun werden Sub-listen erstellt, f√ľr welche ein benutzerdefinierte Untergrenze (eine Zahl zw. 0.0 und 1.0) f√ľr alle m√∂glichen Kombinationen gegeben wird.

              schade, ueberschrieben, morgen neu machen

              Beispiel: Der String 'dresden' w√ľrde die Bigram-Liste ['dr','re','es','sd','de','en'] mit sechs Elementen ergeben. Es w√ľrde sortiert zu ['de','dr','en','es','re','sd'], und bei einer Untergrenze von 0.8 ergebe dies 6 * 0.8 = 4.8, gerundet 5, was bedeutet, dass alle Kombinationen der L√§nge 5 berrechnet werden. F√ľr das gegebene Beispiel

              ['de','dr','en','es','re']

              ['de','dr','en','es','sd']

              ['de','dr','es','re','sd']

              ['de','en','es','re','sd']

              ['de','dr','en','re','sd']

              ['dr','en','es','re','sd']

              Damit wird die korrespondierende Datensatz-Nummer mit den Schl√ľsseln 'dedrenesre', 'dedrenessd', 'dedresresd', 'dedrenresd', 'drenesresd' und 'deenesresd' in die invertierten Index-Bl√∂cke eingef√ľgt.

              Je geringer die Untergrenze, desto k√ľrzer die Sub-Liste, aber umso mehr Sub-Listen gibt es pro Feldwert, was zu mehr (kleineren) Bl√∂cken im invertierten Index f√ľhrt.

              Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme T1 sowie die allgemeine Bigramm-L√§nge T2 identifiziert werden.

              Daraus ergibt sich, wie beim Standard-Blocking, die Komplexität von O(n²/b) [tailor02], wobei b die Anzahl der zu vergleichenden Blöcke darstellt.

              Canopy-Methode

              Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme sowie die allgemeine Bigramm-L√§nge identifiziert werden. Daraus ergibt sich, wie beim Standard-Blocking, die Komplexit√§t von [tailor02], wobei b die Anzahl der zu vergleichenden Bl√∂cke darstellt.

              Diese besteht aus 2 Schritten, wobei der 1. Schritt einen Blockieralgorithmus in der Form darstellt, da√ü er √ľber eine billige Distanzmessung die Entit√§ten in n>= 1 sich √ľberlappende, sog. Canopy (engl. „Abdeckhaube“) einteilt. Dazu wird aus der Liste der Datens√§tze ein beliebiger Eintrag genommen und mit allen anderen Eintr√§gen der Liste verglichen (bspw. nach der Anzahl identischer Attribute). Alle Datens√§tze innerhalb der Distanz werden dabei in ein Canopy gegeben. Alle Datens√§tze innerhalb der Distanz werden von der Liste gel√∂scht. Dies wird wiederholt, bis die Liste leer ist.

              SVG - Suchraumbestimmung - Canopy

              Dadurch werden Nachteile des Grobblockings bzw. Sliding-Windows ausgeräumt, wie ein mögliches Paar außerhalb der Fenstergröße.

              Die „Term-frequency-inverse data frequency“ (TF-IDF) Cosinus √Ąhnlichkeit ist eine billige Distanzmessungen, um sich √ľberlappende Datensatz-Cluster zu erstellen. Es basiert auf der Auftrittsh√§ufigkeit einzelner Terme und wird im Abschnitt [TDIDF] n√§her behandelt.

              Im 2. Schritt werde daraufhin mit einer teureren Distanzmessung nur Punkt-Paare verglichen, welche sich im selben Canopy befinden.

              Bei diesem Ansatz k√∂nnen 3 Parameter gesetzt werden: w√§hrend Stufe 1 der Loose-Grenzwert (T1) und der Tight-Grenzwert (T2) . Bei Verwendung des GAC (siehe unten), 3. Parameter der Stopp-Parameter, bei dessen erreichen keine weitere Iteration ausgef√ľhrt wird.

              Die Berechnungskomplexit√§t kann bei Nutzung der invertierten Liste f√ľr Schritt 2 wie folgt dargestellt werden

              w

              Anzahl der Vergleichsdatensätze

              V

              die möglichen Werte der Attribute, |V| Anzahl der Canopies

              n

              Anzahl aller Entitäten/Datensätze

              O(nw²V)

              Loose und Tight sollten so gewählt werden, daß n gering und |V| möglichst groß ist, um den Umfang der Berechnung zu verringern. bei zu großen Werten können typographische Fehler nicht mehr erkannt werden.

              Zusammenfassung

              Vergleichsmessungen, durchgef√ľhrt in [Kdd03]. Die Ergebniss-Anzahl bei Standard-Blocking k√∂nnen gro√üen Schwankungen unterliegen und nehmen mit zunehmenden Blockierschl√ľsseln rapide ab. Kleinere Bl√∂cke bedeuten dabei zwar weniger Vergleiche, schliessen jedoch ebenso mehr korrekte Paare aus.

              Sorted-Neighbourhood-Methoden verhindern diese Extreme in der Performance des Standard Blockings und erlauben ein vorhersehbares Verhalten durch Erhöhung der Fenstergröße w. Durch größere Fenster erhöht sich die Paar-Vollständigkeit in den Ergebnissen, doch das Reduktionsverhältnis sinkt.

              Mit gut gew√§hlten Parametern sind jedoch sowohl Bigramm- als auch Canopies-Clustering signifikant performanter. Bei Ersterem wird eine Bigram-Vergleichsanzahl von 3 - 4 empfohlen, der Schwellwert f√ľr Canopy sollte um 1.5 liegen.

              . Komplexität korrekte Negative falsche Positive
              Standard-Blocking n²/b ++ ++
              Sliding Window n log n + wn + +
              Bigramme n²/b - +
              Canopy nw²/count(V) - +

          Aus Gr√ľnden der Effizienz und Skalierbarkeit soll ein Vergleich aller Tupel in jeder Relation verhindert werden. Analog zu Schritt 2 aus dem Abschnitt "Strukturanalyse"  wird daher f√ľr jeden Datensatz der Suchraum zur Ableitung m√∂glicher Abbildungen begrenzt.

          Da in der Menge A√óB im Allgemeinen viel mehr Nicht-Treffer als Treffer zu erwarten sind (u(γ)≫m(γ)), werden f√ľr einen Datensatz die Vergleichsdatens√§tze entfernt, welche auf keinen Fall zutreffen. Eine Vielzahl von Methoden haben als Aufgabe, die Rechenkosten der Namensfindung gering zu halten, indem eine erste Grobauswahl aus dem Gesamtdatenbestand isoliert wird. Sets von geordneten Paaren , auf denen der Fellegi-Sunter Verlinkungsalgorithmus Anwendung findet, sind daher mit „Blockierkriterien“ bzw. Sortierschl√ľssel belegt.

          Man nehme als Beispiel ein Tupel-Set, in welchem eine Telefonnummer vorhanden ist. Diese Telefonnummer kann in Verbindung mit einigen wenigen Zeichen des Namens zur Bestimmung von Verlinkungen nutzen. Bei anderen Paaren mögen zusätzlich die Informationen zu Straßennamen und Stadtnamen zugrunde gelegt werden.

          Standard-Blocking

          Der traditionelle Blockier-Algorithmus gruppiert Datens√§tze, wenn diese den selben Inhalt in einer Blockiervariable besitzen, also bspw. den identischen Eintrag f√ľr Stadt und Nachname in einem Datensatz. Blockierkriterien m√ľssen dabei gut gew√§hlt werden, da bei zu allgemeinen Auswahlschl√ľsseln die Menge n√§her zu untersuchender Datens√§tze zu hoch ist (korrekte Negative), bei einer zu engen jedoch passende Datens√§tze ausgesperrt bleiben k√∂nnten (falsche Positive).

          SVG - Suchraumbestimmung - Grobblocking

          Ebenfalls muss die Fehler-Charakteristik des gew√§hlten Schl√ľssels bekannt und ein Fehlerauftritt minimal sein. Durch die Verwendung multipler Blockierschl√ľssel kann der Fehler in einem der Schl√ľssel abgemildert werden. Die Berechnungskomplexit√§t ist pro gew√§hlten Schl√ľssel, O(h(n)+n¬≤/b), wobei h(n) = n log n bei sortierter Blocking-Menge, h(n) = n bei blocking durch hashing. Die Ergebnissmengen sind allerdings nur schwer abzusch√§tzen.

          Sorted-Neighbourhood / sliding window

          Eine Weiterentwicklung stellt die Sorted-Neighbourhood- oder Fenster- Strategie ("windowing strategy") nach [HS95] dar. Sie sortiert einen Datenbestand nach dem Schl√ľssel ("Key")-Attribut mit dem gr√∂√üten Unterschied und vergleicht alle Records innerhalb eines fliessenden Fensters („sliding Window“) in der aussortierten Ordnung . Die Effektivit√§t dieses Ansatzes h√§ngt stark von der Qualit√§t des gew√§hlten Schl√ľssels ab.

          Poor chosen keys will result in a poor quality merge

          Die „Sorted-Neighbourhood“-Methode kann in 3 Phasen zusammengefasst werden:

          1. Erstellen der Schl√ľssel: Errechne einen Schl√ľssel f√ľr jeden Datensatz in der Liste durch extrahieren relevanter Felder oder Feldbestandteile
          2. Sortierung der Daten: Sortiere die Datens√§tze in der Datenliste unter Nutzung des Schl√ľssels aus Schritt 1
          3. Vereine: Bewege ein Fenster mit konstanter Gr√∂√üe durch die sequentielle Liste der Datens√§tze und limitiere den Vergleich auf passende Werte auf solche innerhalb des Fensters. Falls die Fenstergr√∂√üe w Datens√§tze umfasst, so wird jeder neuer Datensatz mit den vorhergehenden w-1 S√§tzen verglichen, um „passende Datens√§tze“ zu finden. Der erste Datensatz im Fenster slided dabei aus dem Fensterbereich.
          SVG - Suchraumbestimmung - Sliding Window

          Bei sehr gro√üen Datenmengen empfiehlt sich ein vorheriges Clustern des Datenbestandes. Dabei wird der Datenbestand in Sequenzen durchsucht, wobei ein n-attributiger Schl√ľssel (Bsp. Nachname+1.Buchstabe des Vornamens) extrahiert und in den n-dimensionalen Clusterraum abgebildet wird.

          Da auch dieses gew√§hlte Attribut einen Fehler besitzen kann, ist ein einzelnes Schl√ľsselattribut zu wenig. Um demnach Fehler im Hauptschl√ľssel auszuschlie√üen, schl√§gt [HS95] folgende Methoden vor:

          1. Durch die Vergrößerung des sliding-windows werden mehr Datensätze mit eingeschlossen.
          2. ein mehrmaliges Ausf√ľhren mit unterschiedlichen Schl√ľsseln und relativ kleinem Fenster gibt, nach einzelnem Abgleich der Ergebniss-Gruppen und transitivem Schlie√üen (nur bei geringer Fenstergr√∂√üe empfehlenswert) die besseren Ergebnisse.

          Als Grenzwerte sind hier die Schl√ľsselanzahl j sowie die Fenstergr√∂√üe w anzugeben. Damit errechnet sich f√ľr n Datens√§tze eine Komplexit√§t von O(i=0j(nlogn+wn)) , wobei O(nlogn) f√ľr die Sortierung ben√∂tigt wird.

          Fuzzy Blocking / Bigramm-Indexing

          Diese Methode basiert auf Bigramme (in [SprachSynth06] auch Diphone oder Halblaute genannt). Die Grundidee dabei besteht darin, dass nach der Indexerstellung die Werte der Blockiervariablen in eine Liste von Bigramme (Diphone, Halblaute) konvertiert werden, welche alphabetisch sortiert und von Duplikaten bereinigt werden. Nun werden Sub-listen erstellt, f√ľr welche ein benutzerdefinierte Untergrenze (eine Zahl zw. 0.0 und 1.0) f√ľr alle m√∂glichen Kombinationen gegeben wird.

          schade, ueberschrieben, morgen neu machen

          Beispiel: Der String 'dresden' w√ľrde die Bigram-Liste ['dr','re','es','sd','de','en'] mit sechs Elementen ergeben. Es w√ľrde sortiert zu ['de','dr','en','es','re','sd'], und bei einer Untergrenze von 0.8 ergebe dies 6 * 0.8 = 4.8, gerundet 5, was bedeutet, dass alle Kombinationen der L√§nge 5 berrechnet werden. F√ľr das gegebene Beispiel

          ['de','dr','en','es','re']

          ['de','dr','en','es','sd']

          ['de','dr','es','re','sd']

          ['de','en','es','re','sd']

          ['de','dr','en','re','sd']

          ['dr','en','es','re','sd']

          Damit wird die korrespondierende Datensatz-Nummer mit den Schl√ľsseln 'dedrenesre', 'dedrenessd', 'dedresresd', 'dedrenresd', 'drenesresd' und 'deenesresd' in die invertierten Index-Bl√∂cke eingef√ľgt.

          Je geringer die Untergrenze, desto k√ľrzer die Sub-Liste, aber umso mehr Sub-Listen gibt es pro Feldwert, was zu mehr (kleineren) Bl√∂cken im invertierten Index f√ľhrt.

          Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme T1 sowie die allgemeine Bigramm-L√§nge T2 identifiziert werden.

          Daraus ergibt sich, wie beim Standard-Blocking, die Komplexität von O(n²/b) [tailor02], wobei b die Anzahl der zu vergleichenden Blöcke darstellt.

          Canopy-Methode

          Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme sowie die allgemeine Bigramm-L√§nge identifiziert werden. Daraus ergibt sich, wie beim Standard-Blocking, die Komplexit√§t von [tailor02], wobei b die Anzahl der zu vergleichenden Bl√∂cke darstellt.

          Diese besteht aus 2 Schritten, wobei der 1. Schritt einen Blockieralgorithmus in der Form darstellt, da√ü er √ľber eine billige Distanzmessung die Entit√§ten in n>= 1 sich √ľberlappende, sog. Canopy (engl. „Abdeckhaube“) einteilt. Dazu wird aus der Liste der Datens√§tze ein beliebiger Eintrag genommen und mit allen anderen Eintr√§gen der Liste verglichen (bspw. nach der Anzahl identischer Attribute). Alle Datens√§tze innerhalb der Distanz werden dabei in ein Canopy gegeben. Alle Datens√§tze innerhalb der Distanz werden von der Liste gel√∂scht. Dies wird wiederholt, bis die Liste leer ist.

          SVG - Suchraumbestimmung - Canopy

          Dadurch werden Nachteile des Grobblockings bzw. Sliding-Windows ausgeräumt, wie ein mögliches Paar außerhalb der Fenstergröße.

          Die „Term-frequency-inverse data frequency“ (TF-IDF) Cosinus √Ąhnlichkeit ist eine billige Distanzmessungen, um sich √ľberlappende Datensatz-Cluster zu erstellen. Es basiert auf der Auftrittsh√§ufigkeit einzelner Terme und wird im Abschnitt [TDIDF] n√§her behandelt.

          Im 2. Schritt werde daraufhin mit einer teureren Distanzmessung nur Punkt-Paare verglichen, welche sich im selben Canopy befinden.

          Bei diesem Ansatz k√∂nnen 3 Parameter gesetzt werden: w√§hrend Stufe 1 der Loose-Grenzwert (T1) und der Tight-Grenzwert (T2) . Bei Verwendung des GAC (siehe unten), 3. Parameter der Stopp-Parameter, bei dessen erreichen keine weitere Iteration ausgef√ľhrt wird.

          Die Berechnungskomplexit√§t kann bei Nutzung der invertierten Liste f√ľr Schritt 2 wie folgt dargestellt werden

          w

          Anzahl der Vergleichsdatensätze

          V

          die möglichen Werte der Attribute, |V| Anzahl der Canopies

          n

          Anzahl aller Entitäten/Datensätze

          O(nw²V)

          Loose und Tight sollten so gewählt werden, daß n gering und |V| möglichst groß ist, um den Umfang der Berechnung zu verringern. bei zu großen Werten können typographische Fehler nicht mehr erkannt werden.

          Zusammenfassung

          Vergleichsmessungen, durchgef√ľhrt in [Kdd03]. Die Ergebniss-Anzahl bei Standard-Blocking k√∂nnen gro√üen Schwankungen unterliegen und nehmen mit zunehmenden Blockierschl√ľsseln rapide ab. Kleinere Bl√∂cke bedeuten dabei zwar weniger Vergleiche, schliessen jedoch ebenso mehr korrekte Paare aus.

          Sorted-Neighbourhood-Methoden verhindern diese Extreme in der Performance des Standard Blockings und erlauben ein vorhersehbares Verhalten durch Erhöhung der Fenstergröße w. Durch größere Fenster erhöht sich die Paar-Vollständigkeit in den Ergebnissen, doch das Reduktionsverhältnis sinkt.

          Mit gut gew√§hlten Parametern sind jedoch sowohl Bigramm- als auch Canopies-Clustering signifikant performanter. Bei Ersterem wird eine Bigram-Vergleichsanzahl von 3 - 4 empfohlen, der Schwellwert f√ľr Canopy sollte um 1.5 liegen.

          . Komplexität korrekte Negative falsche Positive
          Standard-Blocking n²/b ++ ++
          Sliding Window n log n + wn + +
          Bigramme n²/b - +
          Canopy nw²/count(V) - +

      Aus Gr√ľnden der Effizienz und Skalierbarkeit soll ein Vergleich aller Tupel in jeder Relation verhindert werden. Analog zu Schritt 2 aus dem Abschnitt "Strukturanalyse"  wird daher f√ľr jeden Datensatz der Suchraum zur Ableitung m√∂glicher Abbildungen begrenzt.

      Da in der Menge A√óB im Allgemeinen viel mehr Nicht-Treffer als Treffer zu erwarten sind (u(γ)≫m(γ)), werden f√ľr einen Datensatz die Vergleichsdatens√§tze entfernt, welche auf keinen Fall zutreffen. Eine Vielzahl von Methoden haben als Aufgabe, die Rechenkosten der Namensfindung gering zu halten, indem eine erste Grobauswahl aus dem Gesamtdatenbestand isoliert wird. Sets von geordneten Paaren , auf denen der Fellegi-Sunter Verlinkungsalgorithmus Anwendung findet, sind daher mit „Blockierkriterien“ bzw. Sortierschl√ľssel belegt.

      Man nehme als Beispiel ein Tupel-Set, in welchem eine Telefonnummer vorhanden ist. Diese Telefonnummer kann in Verbindung mit einigen wenigen Zeichen des Namens zur Bestimmung von Verlinkungen nutzen. Bei anderen Paaren mögen zusätzlich die Informationen zu Straßennamen und Stadtnamen zugrunde gelegt werden.

      Standard-Blocking

      Der traditionelle Blockier-Algorithmus gruppiert Datens√§tze, wenn diese den selben Inhalt in einer Blockiervariable besitzen, also bspw. den identischen Eintrag f√ľr Stadt und Nachname in einem Datensatz. Blockierkriterien m√ľssen dabei gut gew√§hlt werden, da bei zu allgemeinen Auswahlschl√ľsseln die Menge n√§her zu untersuchender Datens√§tze zu hoch ist (korrekte Negative), bei einer zu engen jedoch passende Datens√§tze ausgesperrt bleiben k√∂nnten (falsche Positive).

      SVG - Suchraumbestimmung - Grobblocking

      Ebenfalls muss die Fehler-Charakteristik des gew√§hlten Schl√ľssels bekannt und ein Fehlerauftritt minimal sein. Durch die Verwendung multipler Blockierschl√ľssel kann der Fehler in einem der Schl√ľssel abgemildert werden. Die Berechnungskomplexit√§t ist pro gew√§hlten Schl√ľssel, O(h(n)+n¬≤/b), wobei h(n) = n log n bei sortierter Blocking-Menge, h(n) = n bei blocking durch hashing. Die Ergebnissmengen sind allerdings nur schwer abzusch√§tzen.

      Sorted-Neighbourhood / sliding window

      Eine Weiterentwicklung stellt die Sorted-Neighbourhood- oder Fenster- Strategie ("windowing strategy") nach [HS95] dar. Sie sortiert einen Datenbestand nach dem Schl√ľssel ("Key")-Attribut mit dem gr√∂√üten Unterschied und vergleicht alle Records innerhalb eines fliessenden Fensters („sliding Window“) in der aussortierten Ordnung . Die Effektivit√§t dieses Ansatzes h√§ngt stark von der Qualit√§t des gew√§hlten Schl√ľssels ab.

      Poor chosen keys will result in a poor quality merge

      Die „Sorted-Neighbourhood“-Methode kann in 3 Phasen zusammengefasst werden:

      1. Erstellen der Schl√ľssel: Errechne einen Schl√ľssel f√ľr jeden Datensatz in der Liste durch extrahieren relevanter Felder oder Feldbestandteile
      2. Sortierung der Daten: Sortiere die Datens√§tze in der Datenliste unter Nutzung des Schl√ľssels aus Schritt 1
      3. Vereine: Bewege ein Fenster mit konstanter Gr√∂√üe durch die sequentielle Liste der Datens√§tze und limitiere den Vergleich auf passende Werte auf solche innerhalb des Fensters. Falls die Fenstergr√∂√üe w Datens√§tze umfasst, so wird jeder neuer Datensatz mit den vorhergehenden w-1 S√§tzen verglichen, um „passende Datens√§tze“ zu finden. Der erste Datensatz im Fenster slided dabei aus dem Fensterbereich.
      SVG - Suchraumbestimmung - Sliding Window

      Bei sehr gro√üen Datenmengen empfiehlt sich ein vorheriges Clustern des Datenbestandes. Dabei wird der Datenbestand in Sequenzen durchsucht, wobei ein n-attributiger Schl√ľssel (Bsp. Nachname+1.Buchstabe des Vornamens) extrahiert und in den n-dimensionalen Clusterraum abgebildet wird.

      Da auch dieses gew√§hlte Attribut einen Fehler besitzen kann, ist ein einzelnes Schl√ľsselattribut zu wenig. Um demnach Fehler im Hauptschl√ľssel auszuschlie√üen, schl√§gt [HS95] folgende Methoden vor:

      1. Durch die Vergrößerung des sliding-windows werden mehr Datensätze mit eingeschlossen.
      2. ein mehrmaliges Ausf√ľhren mit unterschiedlichen Schl√ľsseln und relativ kleinem Fenster gibt, nach einzelnem Abgleich der Ergebniss-Gruppen und transitivem Schlie√üen (nur bei geringer Fenstergr√∂√üe empfehlenswert) die besseren Ergebnisse.

      Als Grenzwerte sind hier die Schl√ľsselanzahl j sowie die Fenstergr√∂√üe w anzugeben. Damit errechnet sich f√ľr n Datens√§tze eine Komplexit√§t von O(i=0j(nlogn+wn)) , wobei O(nlogn) f√ľr die Sortierung ben√∂tigt wird.

      Fuzzy Blocking / Bigramm-Indexing

      Diese Methode basiert auf Bigramme (in [SprachSynth06] auch Diphone oder Halblaute genannt). Die Grundidee dabei besteht darin, dass nach der Indexerstellung die Werte der Blockiervariablen in eine Liste von Bigramme (Diphone, Halblaute) konvertiert werden, welche alphabetisch sortiert und von Duplikaten bereinigt werden. Nun werden Sub-listen erstellt, f√ľr welche ein benutzerdefinierte Untergrenze (eine Zahl zw. 0.0 und 1.0) f√ľr alle m√∂glichen Kombinationen gegeben wird.

      schade, ueberschrieben, morgen neu machen

      Beispiel: Der String 'dresden' w√ľrde die Bigram-Liste ['dr','re','es','sd','de','en'] mit sechs Elementen ergeben. Es w√ľrde sortiert zu ['de','dr','en','es','re','sd'], und bei einer Untergrenze von 0.8 ergebe dies 6 * 0.8 = 4.8, gerundet 5, was bedeutet, dass alle Kombinationen der L√§nge 5 berrechnet werden. F√ľr das gegebene Beispiel

      ['de','dr','en','es','re']

      ['de','dr','en','es','sd']

      ['de','dr','es','re','sd']

      ['de','en','es','re','sd']

      ['de','dr','en','re','sd']

      ['dr','en','es','re','sd']

      Damit wird die korrespondierende Datensatz-Nummer mit den Schl√ľsseln 'dedrenesre', 'dedrenessd', 'dedresresd', 'dedrenresd', 'drenesresd' und 'deenesresd' in die invertierten Index-Bl√∂cke eingef√ľgt.

      Je geringer die Untergrenze, desto k√ľrzer die Sub-Liste, aber umso mehr Sub-Listen gibt es pro Feldwert, was zu mehr (kleineren) Bl√∂cken im invertierten Index f√ľhrt.

      Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme T1 sowie die allgemeine Bigramm-L√§nge T2 identifiziert werden.

      Daraus ergibt sich, wie beim Standard-Blocking, die Komplexität von O(n²/b) [tailor02], wobei b die Anzahl der zu vergleichenden Blöcke darstellt.

      Canopy-Methode

      Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme sowie die allgemeine Bigramm-L√§nge identifiziert werden. Daraus ergibt sich, wie beim Standard-Blocking, die Komplexit√§t von [tailor02], wobei b die Anzahl der zu vergleichenden Bl√∂cke darstellt.

      Diese besteht aus 2 Schritten, wobei der 1. Schritt einen Blockieralgorithmus in der Form darstellt, da√ü er √ľber eine billige Distanzmessung die Entit√§ten in n>= 1 sich √ľberlappende, sog. Canopy (engl. „Abdeckhaube“) einteilt. Dazu wird aus der Liste der Datens√§tze ein beliebiger Eintrag genommen und mit allen anderen Eintr√§gen der Liste verglichen (bspw. nach der Anzahl identischer Attribute). Alle Datens√§tze innerhalb der Distanz werden dabei in ein Canopy gegeben. Alle Datens√§tze innerhalb der Distanz werden von der Liste gel√∂scht. Dies wird wiederholt, bis die Liste leer ist.

      SVG - Suchraumbestimmung - Canopy

      Dadurch werden Nachteile des Grobblockings bzw. Sliding-Windows ausgeräumt, wie ein mögliches Paar außerhalb der Fenstergröße.

      Die „Term-frequency-inverse data frequency“ (TF-IDF) Cosinus √Ąhnlichkeit ist eine billige Distanzmessungen, um sich √ľberlappende Datensatz-Cluster zu erstellen. Es basiert auf der Auftrittsh√§ufigkeit einzelner Terme und wird im Abschnitt [TDIDF] n√§her behandelt.

      Im 2. Schritt werde daraufhin mit einer teureren Distanzmessung nur Punkt-Paare verglichen, welche sich im selben Canopy befinden.

      Bei diesem Ansatz k√∂nnen 3 Parameter gesetzt werden: w√§hrend Stufe 1 der Loose-Grenzwert (T1) und der Tight-Grenzwert (T2) . Bei Verwendung des GAC (siehe unten), 3. Parameter der Stopp-Parameter, bei dessen erreichen keine weitere Iteration ausgef√ľhrt wird.

      Die Berechnungskomplexit√§t kann bei Nutzung der invertierten Liste f√ľr Schritt 2 wie folgt dargestellt werden

      w

      Anzahl der Vergleichsdatensätze

      V

      die möglichen Werte der Attribute, |V| Anzahl der Canopies

      n

      Anzahl aller Entitäten/Datensätze

      O(nw²V)

      Loose und Tight sollten so gewählt werden, daß n gering und |V| möglichst groß ist, um den Umfang der Berechnung zu verringern. bei zu großen Werten können typographische Fehler nicht mehr erkannt werden.

      Zusammenfassung

      Vergleichsmessungen, durchgef√ľhrt in [Kdd03]. Die Ergebniss-Anzahl bei Standard-Blocking k√∂nnen gro√üen Schwankungen unterliegen und nehmen mit zunehmenden Blockierschl√ľsseln rapide ab. Kleinere Bl√∂cke bedeuten dabei zwar weniger Vergleiche, schliessen jedoch ebenso mehr korrekte Paare aus.

      Sorted-Neighbourhood-Methoden verhindern diese Extreme in der Performance des Standard Blockings und erlauben ein vorhersehbares Verhalten durch Erhöhung der Fenstergröße w. Durch größere Fenster erhöht sich die Paar-Vollständigkeit in den Ergebnissen, doch das Reduktionsverhältnis sinkt.

      Mit gut gew√§hlten Parametern sind jedoch sowohl Bigramm- als auch Canopies-Clustering signifikant performanter. Bei Ersterem wird eine Bigram-Vergleichsanzahl von 3 - 4 empfohlen, der Schwellwert f√ľr Canopy sollte um 1.5 liegen.

      . Komplexität korrekte Negative falsche Positive
      Standard-Blocking n²/b ++ ++
      Sliding Window n log n + wn + +
      Bigramme n²/b - +
      Canopy nw²/count(V) - +

Aus Gr√ľnden der Effizienz und Skalierbarkeit soll ein Vergleich aller Tupel in jeder Relation verhindert werden. Analog zu Schritt 2 aus dem Abschnitt "Strukturanalyse"  wird daher f√ľr jeden Datensatz der Suchraum zur Ableitung m√∂glicher Abbildungen begrenzt.

Da in der Menge A√óB im Allgemeinen viel mehr Nicht-Treffer als Treffer zu erwarten sind (u(γ)≫m(γ)), werden f√ľr einen Datensatz die Vergleichsdatens√§tze entfernt, welche auf keinen Fall zutreffen. Eine Vielzahl von Methoden haben als Aufgabe, die Rechenkosten der Namensfindung gering zu halten, indem eine erste Grobauswahl aus dem Gesamtdatenbestand isoliert wird. Sets von geordneten Paaren , auf denen der Fellegi-Sunter Verlinkungsalgorithmus Anwendung findet, sind daher mit „Blockierkriterien“ bzw. Sortierschl√ľssel belegt.

Man nehme als Beispiel ein Tupel-Set, in welchem eine Telefonnummer vorhanden ist. Diese Telefonnummer kann in Verbindung mit einigen wenigen Zeichen des Namens zur Bestimmung von Verlinkungen nutzen. Bei anderen Paaren mögen zusätzlich die Informationen zu Straßennamen und Stadtnamen zugrunde gelegt werden.

Standard-Blocking

Der traditionelle Blockier-Algorithmus gruppiert Datens√§tze, wenn diese den selben Inhalt in einer Blockiervariable besitzen, also bspw. den identischen Eintrag f√ľr Stadt und Nachname in einem Datensatz. Blockierkriterien m√ľssen dabei gut gew√§hlt werden, da bei zu allgemeinen Auswahlschl√ľsseln die Menge n√§her zu untersuchender Datens√§tze zu hoch ist (korrekte Negative), bei einer zu engen jedoch passende Datens√§tze ausgesperrt bleiben k√∂nnten (falsche Positive).

SVG - Suchraumbestimmung - Grobblocking

Ebenfalls muss die Fehler-Charakteristik des gew√§hlten Schl√ľssels bekannt und ein Fehlerauftritt minimal sein. Durch die Verwendung multipler Blockierschl√ľssel kann der Fehler in einem der Schl√ľssel abgemildert werden. Die Berechnungskomplexit√§t ist pro gew√§hlten Schl√ľssel, O(h(n)+n¬≤/b), wobei h(n) = n log n bei sortierter Blocking-Menge, h(n) = n bei blocking durch hashing. Die Ergebnissmengen sind allerdings nur schwer abzusch√§tzen.

Sorted-Neighbourhood / sliding window

Eine Weiterentwicklung stellt die Sorted-Neighbourhood- oder Fenster- Strategie ("windowing strategy") nach [HS95] dar. Sie sortiert einen Datenbestand nach dem Schl√ľssel ("Key")-Attribut mit dem gr√∂√üten Unterschied und vergleicht alle Records innerhalb eines fliessenden Fensters („sliding Window“) in der aussortierten Ordnung . Die Effektivit√§t dieses Ansatzes h√§ngt stark von der Qualit√§t des gew√§hlten Schl√ľssels ab.

Poor chosen keys will result in a poor quality merge

Die „Sorted-Neighbourhood“-Methode kann in 3 Phasen zusammengefasst werden:

  1. Erstellen der Schl√ľssel: Errechne einen Schl√ľssel f√ľr jeden Datensatz in der Liste durch extrahieren relevanter Felder oder Feldbestandteile
  2. Sortierung der Daten: Sortiere die Datens√§tze in der Datenliste unter Nutzung des Schl√ľssels aus Schritt 1
  3. Vereine: Bewege ein Fenster mit konstanter Gr√∂√üe durch die sequentielle Liste der Datens√§tze und limitiere den Vergleich auf passende Werte auf solche innerhalb des Fensters. Falls die Fenstergr√∂√üe w Datens√§tze umfasst, so wird jeder neuer Datensatz mit den vorhergehenden w-1 S√§tzen verglichen, um „passende Datens√§tze“ zu finden. Der erste Datensatz im Fenster slided dabei aus dem Fensterbereich.
SVG - Suchraumbestimmung - Sliding Window

Bei sehr gro√üen Datenmengen empfiehlt sich ein vorheriges Clustern des Datenbestandes. Dabei wird der Datenbestand in Sequenzen durchsucht, wobei ein n-attributiger Schl√ľssel (Bsp. Nachname+1.Buchstabe des Vornamens) extrahiert und in den n-dimensionalen Clusterraum abgebildet wird.

Da auch dieses gew√§hlte Attribut einen Fehler besitzen kann, ist ein einzelnes Schl√ľsselattribut zu wenig. Um demnach Fehler im Hauptschl√ľssel auszuschlie√üen, schl√§gt [HS95] folgende Methoden vor:

  1. Durch die Vergrößerung des sliding-windows werden mehr Datensätze mit eingeschlossen.
  2. ein mehrmaliges Ausf√ľhren mit unterschiedlichen Schl√ľsseln und relativ kleinem Fenster gibt, nach einzelnem Abgleich der Ergebniss-Gruppen und transitivem Schlie√üen (nur bei geringer Fenstergr√∂√üe empfehlenswert) die besseren Ergebnisse.

Als Grenzwerte sind hier die Schl√ľsselanzahl j sowie die Fenstergr√∂√üe w anzugeben. Damit errechnet sich f√ľr n Datens√§tze eine Komplexit√§t von O(i=0j(nlogn+wn)) , wobei O(nlogn) f√ľr die Sortierung ben√∂tigt wird.

Fuzzy Blocking / Bigramm-Indexing

Diese Methode basiert auf Bigramme (in [SprachSynth06] auch Diphone oder Halblaute genannt). Die Grundidee dabei besteht darin, dass nach der Indexerstellung die Werte der Blockiervariablen in eine Liste von Bigramme (Diphone, Halblaute) konvertiert werden, welche alphabetisch sortiert und von Duplikaten bereinigt werden. Nun werden Sub-listen erstellt, f√ľr welche ein benutzerdefinierte Untergrenze (eine Zahl zw. 0.0 und 1.0) f√ľr alle m√∂glichen Kombinationen gegeben wird.

schade, ueberschrieben, morgen neu machen

Beispiel: Der String 'dresden' w√ľrde die Bigram-Liste ['dr','re','es','sd','de','en'] mit sechs Elementen ergeben. Es w√ľrde sortiert zu ['de','dr','en','es','re','sd'], und bei einer Untergrenze von 0.8 ergebe dies 6 * 0.8 = 4.8, gerundet 5, was bedeutet, dass alle Kombinationen der L√§nge 5 berrechnet werden. F√ľr das gegebene Beispiel

['de','dr','en','es','re']

['de','dr','en','es','sd']

['de','dr','es','re','sd']

['de','en','es','re','sd']

['de','dr','en','re','sd']

['dr','en','es','re','sd']

Damit wird die korrespondierende Datensatz-Nummer mit den Schl√ľsseln 'dedrenesre', 'dedrenessd', 'dedresresd', 'dedrenresd', 'drenesresd' und 'deenesresd' in die invertierten Index-Bl√∂cke eingef√ľgt.

Je geringer die Untergrenze, desto k√ľrzer die Sub-Liste, aber umso mehr Sub-Listen gibt es pro Feldwert, was zu mehr (kleineren) Bl√∂cken im invertierten Index f√ľhrt.

Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme T1 sowie die allgemeine Bigramm-L√§nge T2 identifiziert werden.

Daraus ergibt sich, wie beim Standard-Blocking, die Komplexität von O(n²/b) [tailor02], wobei b die Anzahl der zu vergleichenden Blöcke darstellt.

Canopy-Methode

Als Grenzwerte kann hier die Anzahl der √ľbereinstimmenden Bigramme sowie die allgemeine Bigramm-L√§nge identifiziert werden. Daraus ergibt sich, wie beim Standard-Blocking, die Komplexit√§t von [tailor02], wobei b die Anzahl der zu vergleichenden Bl√∂cke darstellt.

Diese besteht aus 2 Schritten, wobei der 1. Schritt einen Blockieralgorithmus in der Form darstellt, da√ü er √ľber eine billige Distanzmessung die Entit√§ten in n>= 1 sich √ľberlappende, sog. Canopy (engl. „Abdeckhaube“) einteilt. Dazu wird aus der Liste der Datens√§tze ein beliebiger Eintrag genommen und mit allen anderen Eintr√§gen der Liste verglichen (bspw. nach der Anzahl identischer Attribute). Alle Datens√§tze innerhalb der Distanz werden dabei in ein Canopy gegeben. Alle Datens√§tze innerhalb der Distanz werden von der Liste gel√∂scht. Dies wird wiederholt, bis die Liste leer ist.

SVG - Suchraumbestimmung - Canopy

Dadurch werden Nachteile des Grobblockings bzw. Sliding-Windows ausgeräumt, wie ein mögliches Paar außerhalb der Fenstergröße.

Die „Term-frequency-inverse data frequency“ (TF-IDF) Cosinus √Ąhnlichkeit ist eine billige Distanzmessungen, um sich √ľberlappende Datensatz-Cluster zu erstellen. Es basiert auf der Auftrittsh√§ufigkeit einzelner Terme und wird im Abschnitt [TDIDF] n√§her behandelt.

Im 2. Schritt werde daraufhin mit einer teureren Distanzmessung nur Punkt-Paare verglichen, welche sich im selben Canopy befinden.

Bei diesem Ansatz k√∂nnen 3 Parameter gesetzt werden: w√§hrend Stufe 1 der Loose-Grenzwert (T1) und der Tight-Grenzwert (T2) . Bei Verwendung des GAC (siehe unten), 3. Parameter der Stopp-Parameter, bei dessen erreichen keine weitere Iteration ausgef√ľhrt wird.

Die Berechnungskomplexit√§t kann bei Nutzung der invertierten Liste f√ľr Schritt 2 wie folgt dargestellt werden

w

Anzahl der Vergleichsdatensätze

V

die möglichen Werte der Attribute, |V| Anzahl der Canopies

n

Anzahl aller Entitäten/Datensätze

O(nw²V)

Loose und Tight sollten so gewählt werden, daß n gering und |V| möglichst groß ist, um den Umfang der Berechnung zu verringern. bei zu großen Werten können typographische Fehler nicht mehr erkannt werden.

Zusammenfassung

Vergleichsmessungen, durchgef√ľhrt in [Kdd03]. Die Ergebniss-Anzahl bei Standard-Blocking k√∂nnen gro√üen Schwankungen unterliegen und nehmen mit zunehmenden Blockierschl√ľsseln rapide ab. Kleinere Bl√∂cke bedeuten dabei zwar weniger Vergleiche, schliessen jedoch ebenso mehr korrekte Paare aus.

Sorted-Neighbourhood-Methoden verhindern diese Extreme in der Performance des Standard Blockings und erlauben ein vorhersehbares Verhalten durch Erhöhung der Fenstergröße w. Durch größere Fenster erhöht sich die Paar-Vollständigkeit in den Ergebnissen, doch das Reduktionsverhältnis sinkt.

Mit gut gew√§hlten Parametern sind jedoch sowohl Bigramm- als auch Canopies-Clustering signifikant performanter. Bei Ersterem wird eine Bigram-Vergleichsanzahl von 3 - 4 empfohlen, der Schwellwert f√ľr Canopy sollte um 1.5 liegen.

. Komplexität korrekte Negative falsche Positive
Standard-Blocking n²/b ++ ++
Sliding Window n log n + wn + +
Bigramme n²/b - +
Canopy nw²/count(V) - +
top