Pass-Join

Als wesentliche Operation in der Datenbereinigung hat der Similarity Join beträchtliche Aufmerksamkeit von der Datenbankgemeinschaft erregt. In diesem Papier untersuchen wir String-Similarity-Joins mit Edit-Distanz-Beschränkungen, die ähnliche String-Paare aus zwei großen Mengen von Strings finden, deren Edit-Distanz innerhalb eines gegebenen Schwellenwerts liegt. Existierende Algorithmen sind entweder effizient für kurze Strings oder für lange Strings, und es gibt keinen Algorithmus, der effizient und adaptiv sowohl kurze als auch lange Strings unterstützen kann. Um dieses Problem anzugehen, schlagen wir eine partitionierungsbasierte Methode namens Pass-Join vor. Pass-Join partitioniert einen String in eine Menge von Segmenten und erstellt invertierte Indizes für die Segmente. Dann wählt Pass-Join für jeden String einige seiner Teilstrings aus und verwendet die ausgewählten Teilstrings, um Kandidatenpaare mithilfe der invertierten Indizes zu finden. Wir entwickeln effiziente Techniken zur Auswahl der Teilstrings und beweisen, dass unsere Methode die Anzahl der ausgewählten Teilstrings minimieren kann. Wir entwickeln neuartige Beschneidungstechniken, um die Kandidatenpaare effizient zu verifizieren. Experimentelle Ergebnisse zeigen, dass unsere Algorithmen sowohl für kurze als auch für lange Strings effizient sind und die besten verfügbaren Methoden bei realen Datensätzen übertreffen.