Performance-Steigerung in Semantik-basierten Abfrage-Systemen

Abstract

Ein Frage-Antwort System benutzt Algorithmen um semantisch ähnliche Fragen zu finden. Diese benötigen durch ihre hohe algorithmische Komplexität mehrere Sekunden für eine Berechnung. Das Matching soll jedoch in einer Anwendung eingesetzt werden, in der dem Benutzer oder der Benutzerin die Resultate in Echtzeit präsentiert werden. Damit diese Anforderung erfüllt werden kann schlägt diese Arbeit eine Vorberechnung von Ähnlichkeiten vor, deren Ergebnisse in einer geeigneten Datenstruktur abgelegt und anschließend dazu benutzt werden um in wenigen Millisekunden Antworten generieren zu können. Die Matching-Algorithmen verwenden Schlüsselwörter für ihre Berechnungen. Folglich entspricht die Menge aller Kombinationen dieser Keywords allen theoretisch denkbaren Eingaben. Da nicht all diese Möglichkeiten berechnet werden können, ist ein zentraler Punkt, eine sinnvolle Einschränkung zu treffen. Der Ansatz, der im Zug dieser Arbeit vorgestellt wird, verbindet nur Schlüsselwörter miteinander, bei denen die Schnittmenge der Matches nicht leer ist. Alle berechneten Ähnlichkeiten werden in einer Lucene-Indexstruktur gespeichert. Um dem Benutzer oder der Benutzerin die ähnlichsten Fragen präsentieren zu können, auch wenn noch kein Schlüsselwort komplett eingetippt wurde oder Tippfehler in der Eingabe vorhanden sind, werden die Vorberechnungen zusätzlich mit einer syntaktischen Suche kombiniert.

A given Query Answering System uses algorithms in order to find semantically similar questions. Due to the high algorithmic complexity the calculations require a couple of seconds. However, the matching should be used in an application which should be able to present the results in real time. To meet these requirements this thesis proposes some sort of pre-calculation of similarities. The results are stored in a suitable data structure and as a result they are used to generate answers in a few milliseconds. For their calculations the matching algorithms are using keywords. Consequently, the set of all combinations of keywords would contain all theoretically possible inputs. Due to the fact that it is impossible to calculate all those some useful restrictions are needed. The approach presented in this work only combines keywords with an intersecting set of matches. All calculated similarities are stored in a Lucene index structure. In order to present the most similar questions to the user, even if the input contains no keyword or contains typographical errors, these pre-computations are combined with the results of a syntactic search.