Konzepte und Realisierung einer kontextbasierten Intranet-Suchmaschine

Abstract

Suchmaschinen sind ein wichtiges Werkzeug zur Recherche von Dokumenten - nicht nur im World Wide Web, sondern gleichermaßen im Intranet von Unternehmen. Herkömmliche Dokumentensuchmaschinen werten zur Beantwortung von Suchanfragen lediglich den Inhalt, d.h. den Text der Dokumente aus. Der Ansatz der vorliegenden Arbeit basiert darauf, dass nicht nur der Text sondern ebenfalls der Kontext der Dokumente in die Auswertung miteinbezogen wird. Die Kontextinformation der Dokumente wird dazu aus den Datenbanken des Unternehmens extrahiert. Die kontextbasierte Suche ist dabei nicht als Alternative zu herkömmlicher, textbasierter Suche zu sehen, sondern als eine Erweiterung. Wie bei vielen Suchmaschinen üblich, spezifiziert der Benutzer den jeweiligen Informationsbedarf nicht als Ausdruck einer formalen Sprache, sondern als Schlüsselwortanfrage. Zur Bestimmung der Dokumentenkontexte und als Abstraktion von Unternehmensdatenbanken wird ein graphenbasiertes Modell eingeführt, der ContextGraph. Die Knoten des ContextGraph repräsentieren einerseits Datenbankdaten und andererseits die vom System erfassten Dokumente. Die Kanten des ContextGraph modellieren Fremdschlüsselbeziehungen bzw. Beziehungen zwischen Tupeln und Attributwerten in der Datenbank. Jede Kante ist gewichtet mit einem Maß für den inhaltlichen bzw. semantischen Abstand der beiden Knoten die durch sie verbunden sind. Der ContextGraph bildet die Basis zur Berechnung des Kontexts von Dokumenten, welcher durch eine inkrementelle Kürzeste-Wege-Suche im ContextGraph bestimmt wird. Bei der Bearbeitung von Suchanfragen und bei der Bewertung der Resultate wird nicht nur der Text sondern zusätzlich der Kontext von Dokumenten, d.h. die im Kontext der Dokumente enthaltenenen Begriffe berücksichtigt. Um dies zu ermöglichen werden Bewertungsmaße für die kontextbasierte Relevanz von Dokumenten bzgl. Suchbegriffen, für die kontextbasierte Wichtigkeit von Dokumenten und für die kontextbasierte Ähnlichkeit von Dokumenten entworfen. Diese Bewertungsmaße werden umgesetzt als eine Erweiterung des im Suchmaschinenbereich bewährten tf.idf-Bewertungsmaßes zur Bestimmung der Begriffsgewichte im Vektorraummodell. Um den Ansatz praktisch zu erproben wird eine Architektur entworfen und darauf aufbauend ein prototypisches System zur kontextbasierten Suche implementiert. Damit Skalierbarkeit erreicht werden kann, verfolgt die Suchmaschine den indexbasierten Ansatz. Zur Indexierungszeit wird der Datenbestand erhoben und in Datenstrukturen, sog. Indexen, abgelegt, die eine effiziente Verarbeitung von Suchanfragen zur Anfragezeit unterstützen. Das implementierte System wird anhand zweier Szenarien analysiert. Dafür werden jeweils alternative Implementierungen der kontextbasierten Suche mit einer Implementierung der rein textbasierten Suche verglichen. Besonderes Augenmerk gilt dabei der Skalierbarkeit des Systems und einem Parameter zur Einstellung der vom System beachteten Kontextgröße. Die Messergebnisse quantifizieren einerseits den durch die Betrachtung des Kontexts nötigen Mehraufwand gegenüber der Textsuche. Andererseits wird die Qualität der Suchergebnisse analysiert. Die Auswertung der Messergebnisse belegen einen moderaten durch die Beachtung des Kontexts hervorgerufenen Mehraufwand, der sich - je nach Implementierung der Indexstrukturen - mehr im Aufwand zur Bearbeitung von Suchanfragen oder mehr im Aufwand bei der Erstellung des Index niederschlägt. In beiden analysierten Szenarien ergibt sich demgegenüber jedoch eine durch die Beachtung von Kontextinformation deutliche Verbesserung der Qualität der Suchresultate.

Search engines are important tools for document retrieval. This is not only true in the World Wide Web, but also in the enterprise intranet. To process search requests and, in particular, rank the search results, standard search engines use mainly the text, i.e. the content of documents. In this work, we present an approach that is not restricted to document content, but additionally exploits document context. To this end, we derive the context of documents from the enterprise's databases. We do not consider the context-based document retrieval to be an alternative to common, text-based retrieval but rather to be an extension. As in many popular and established search engines the user specifies his information need not as a formal-language expression but as a list of search keywords. As an abstraction of enterprise databases and as a basis to compute document contexts, we introduce a graph-based data model, which we call ContextGraph. On the one hand, ContextGraph nodes represent database entities and attribute values. On the other hand, they also model documents. Edges in the ContextGraph represent foreign-key relationships and relationships between tuples and attribute values in the database. Edges are directed and carry a measure that denotes the directed semantic distance between their two adjacent nodes. Based on the ContextGraph we determine the contexts of documents by means of an greedy shortest-paths algorithm. To process search requests and to rank the search results we do not only consider keywords from the documents' content but also from their context. To this end we introduce ranking measures for context-based relevance of documents concerning a given keyword search query, for context-based document importance, and for context-based document similarity. These measures we implement as an extension to the tf.idf measure that calculates term-weights in the vector-space model. Both, tf.idf, and the vector-space model are well-known and proven concepts in the area of information retrieval. As a proof of concept, we present an architecture and explain how we implemented our prototype system that realizes a context-based search engine. To enable scalability the system follows the index-based approach. At indexing time, the it analyzes the enterprise's data and builds a data structure, the index, that supports efficient query processing at query time. We analyze and evaluate our system based on two scenarios. To this end, we compare three alternative implementations of the context-based search engine with a pure text-based search engine. In particular, we focus on the scalability of the system and on the influence of an important parameter that adjusts the size of the evaluated context. On the one hand, our measurements quantify the overhead of context-based search as opposed to pure text-based search. On the other hand, we analyze the quality of search results. Evaluations of our measurements show that the performance overhead is moderate. Depending on the implementation of the index, the emphasis of overhead can be placed either at indexing time or at query time. Furthermore, our evaluations on both analyzed scenarios demonstrate that the overhead is not in vain. Compared with the text-based search engine, the context-based engine shows a significant increase in the quality of search results.