FFTED - Schnelle und flexible Edit-Distanz für Baumdaten

Hierarchisch strukturierte Daten werden Bäume genannt. Ein Beispiel ist die hierarchische Organisation eines Unternehmens mit Abteilungen, Führungskräften und Mitarbeitern. Weitere Beispiele sind Anlagegüter von Unternehmen, Materialstücklisten, Syntaxbäume von natürlichen Sprachen oder Programmiersprachen, Dateiordner in Dateisystemen, sowie molekulare Strukturen in der Bioinformatik. Wenn sich Baumdaten ändern, werden neue Baumversion erzeugt. Die Differenzen zwischen zwei Versionen (auch als Diffs bezeichnet) festzustellen ist eine wichtige Aufgabe. Gute Diffs sind so prägnant wie möglich. Ein weit verbreiteter Ansatz ist die Edit-Distanz, welche das kleinstmögliche Diff berechnet. Die Berechnung des minimalen Diffs ist schwierig. Die derzeitigen Lösungen kranken an mangelnder Effizienz und Flexibilität, was deren praktischen Einsatz stark einschränkt. (1) Effizienz: Die Berechnung des minimalen Diffs ist zu langsam. Bei doppelter Baumgröße braucht die Berechnung mindestens vier mal so lang. Gängige Techniken sind für Bäume mit etwa 10.000 Elementen anwendbar, aber viele interessante Bäume bestehen aus Millionen von Elementen (z.B. Materialstücklisten). (2) Flexibilität: Die Edit-Distanz berechnet das kleinstmögliche Diff und ignoriert jedwede Anwendungssemantik, was zu nicht-intuitiven Ergebnissen führen kann, z.B. könnte eine Abteilung in einen Mitarbeiter umgewandelt werden, um das Diff klein zu halten. Verschiedene Lösungsversuche sind unternommen worden, die jedoch alle mindestens eine der folgenden Einschränkungen mit sich bringen: für mehr Geschwindigkeit muss Qualität geopfert werden (d.h. die Diffs sind unnötig lang) und der Qualitätsverlust wird nicht quantifiziert; die Anwendungssemantik ist fest in die Lösung eingebaut, was deren Einsatzfähigkeit auf sehr spezifische Anwendungen beschränkt; oder nur eines der beiden Probleme (Effizienz oder Flexibilität) wird angegangen. Ziel dieses Projektes ist es, die Effizienz- und Flexibilitätsprobleme der Edit-Distanz zu lösen ohne Qualität einzubüßen. Wir werden erlauben, anwendungsspezifische Bedingungen als Teil des Input zu formulieren (z.B. Abteilungen können nicht zu Mitarbeitern gemacht werden), und das minimale Diff, welches diese Bedingungen erfüllt, wird berechnet. Diese Flexibilität wird unsere Lösung für weite Anwendungsbereiche zugänglich machen. Um Effizienz zu erreichen, planen wir zwei bisher wenig beachtete Tatsachen zu nutzen: Zum einen betreffen Änderungen typischerweise nur kleine Bereiche eines Baumes.Indemwir uns aufdiese Bereiche konzentrieren, hoffen wir auf erhebliche Geschwindigkeitsvorteile. Zum anderen schränken Bedingungen die Anzahl der möglichen Diffs ein, was wir ebenfalls zur Steigerung der Effizienz nutzen wollen. Im Erfolgsfall wird unsere Lösung die erste Edit-Distanz mit benutzerdefinierten Bedingungen sein, welche das kleinstmögliche Diff effizient berechnen kann.

Ziel dieses Projekts war die Entwicklung von effizienten Techniken zur Beantwortung von Ähnlichkeitsanfragen über baumstrukturierte Daten. Die Baumstruktur von Daten ergibt sich durch hierarchische Abhängigkeiten, zum Beispiel gehört ein Autor immer zum dazugehörigen Buch und muss in diesem Kontext betrachtet werden. Die Vielzahl der Anwendungen, die baumstrukturierte Daten erfordern, führte zur Entwicklung von hierarchischen Datenformaten wie XML und JSON. Eine häufig gestellte Anfrage ermittelt Datenbäume basierend auf ihrer paarweisen Ähnlichkeit, welche durch die minimale Differenz zwischen den Bäumen definiert wird: der sogenannten Tree Edit Distance (TED). Anfragen mit TED führen zwar zu intuitiven Ergebnissen, sind aber zeitintensiv in der Berechnung aufgrund fehlender, effizienter Techniken zur Beantwortung dieser Anfragen. In diesem Projekt wurden mehrere neue Ansätze für gängige Ähnlichkeitsanfragen entwickelt, die den aktuellen Stand der Forschung erweitern und bisherige Lösungen in Bezug auf Laufzeit und Speicherverbrauch erheblich verbessern. (1) TopDiff: Oft muss die minimale Differenz zwischen Paaren von Bäumen berechnet werden, was jedoch eine kostspielige Operation darstellt. Der in diesem Projekt entwickelte TopDiff Algorithmus nützt die Ähnlichkeit der Bäume um die Berechnungszeit drastisch zu reduzieren. Die Berechnungszeit für ähnliche Bäume wächst linear in der Baumgröße, während bestehende TED Algorithmen ein kubisches Wachstum aufweisen. (2) SlimCone: Die Top-k Subtree Similarity Anfrage berechnet die k ähnlichsten Teilbäume eines Dokumentbaumes für einen gegebenen Anfragebaum. Bisherige Lösungen basieren auf Indextechniken mit großem Speicherverbrauch, was die Anwendbarkeit auf kleine Bäume einschränkt. Der im Projekt entwickelte SlimCone Index basiert auf einer neuen Idee, welche sowohl den Speicherverbrauch reduziert als auch die Berechnungszeit verringert. (3) TJoin: Der Tree Similarity Join identifiziert alle Baumpaare in einer Menge von Bäumen, welche einen TED Wert kleiner als einen benutzerdefinierten Grenzwert aufweisen. Diese Anfrage wird üblicherweise benutzt, um Duplikate in Daten zu identifizieren. Alle Baumpaare zu vergleichen skaliert nicht für große Datenmengen. Der von uns entwickelte TJoin Algorithmus nutzt einen Index und effiziente aber effektive Filtertechniken um einen Großteil der paarweisen TED Berechnungen zu vermeiden. Alle Paare, welche die Filter passieren, werden von einem neuen Verifikationsalgorithmus überprüft, der den gegebenen Grenzwert ausnutzt um die teuren TED Berechnungen zu vermeiden. Alle in diesem Projekt entwickelten Techniken wurden experimentell mit den bestehenden Lösungen verglichen; die Ergebnisse zeigen, dass die neuen Techniken gegenüber konkurrierenden Lösungen für große Datenmengen oft Laufzeitverbesserungen von mehreren Größenordnungen bringen.