Cooperatively Managing and Exploiting Distributed Co-occurrence Graphs
The property of terms to occur adjacently, or in close vicinity, in text corpora can be expressed by co-occurrence graphs. Such data structures proved to be useful tools to extract semantic information in natural language processing and information retrieval. Particularly when organisations and communities work collaboratively on joint documents and corpora, the corresponding co-occurrence graphs may grow prohibitively large to be handled on a single machine. Hence, methods are devised to cooperatively distribute and process co-occurrence graphs in peer-to-peer computing environments, whose performance shows a near-linear speed-up as compared to the capability of a single processor. Moreover, in each peer, a local co-occurrence graph is built from documents of the users attached to the peer and obtained from elsewhere. These local graphs are used to calculate text centroids from terms contained in them as unique document identifiers and as search keys in queries. They are also useful in reducing the amount of broadcast traffic. Routing and load imbalance of inter-peer traffic are reduced by bio-inspired algorithms designed to work with limited information available on peers locally or on their direct neighbours. Thus, routing paths directly leading to the final destinations are determined in most cases, and memory usage is balanced after a few message exchanges. To show that decentralised co-occurrence graphs can be employed as the basis of a fully integrated, decentralised search engine, a prototype working on the world wide web is built, implemented, and experimentally evaluated. This search engine uses text centroids to represent short word groups constituting queries as well as long texts in crawling the web for information and for matching queries with documents.
Die Eigenschaft von Begriffen, in Textkorpora nebeneinander oder in unmittelbarer Nähe aufzutreten, wird üblicherweise durch Kookkurrenzgraphen modelliert. Derartige Strukturen haben sich als nützliche Werkzeuge zur Extraktion semantischer Informationen in der Verarbeitung natürlicher Sprache und im Information Retrieval bewährt. Arbeiten Organisationen und Gemeinschaften gemeinsam an Dokumenten und Korpora, können die entsprechenden Kookkurrenzgraphen jedoch so groß werden, dass sie auf einer einzelnen Maschine nicht mehr verarbeitet werden können. Daher werden in der ARbeit zunächst Methoden entwickelt, um Kookkurrenzgraphen in Peer-to-Peer-Umgebun- gen kooperativ zu erstellen und zu verarbeiten. Diese Verarbeitungsumgebungen ermöglichen hierbei durch ihre Leistung eine nahezu lineare Beschleunigung im Vergleich zu den Fähigkeiten eines einzelnen Prozessors aufweist. Darüber hinaus wird durch das System für jeden Peer ein lokaler Kookkurrenzgraph verwaltet, der aus den Dokumenten der Benutzer, die dem Peer zugeordnet sind, und ggf. aus weiteren, interessanten Quellen erstellt wird. Diese lokalen Graphen werden verwendet, um Zentroide zu berechnen, die dann als einzelner Term eine Dokumentenkennung und als Suchschlüssel in Abfragen dient. Sie enthalten ferner nützliche Informationen, um den Umfang von Broadcasts zu verringern. Routing und Lastungleichgewichte zwischen den Peers werden durch biologisch inspirierte Algorithmen verbessert bzw. reduziert, die mit begrenzten Informationen von dem lokalen Peers bzw. seiner direkten Nachbarn arbeiten. Damit können in den meisten Fällen Routingpfade ermittelt werden, die auf optimalen Wegen zu den Endzielen führen; in Bezug auf die Speichernutzung kann hierdurch nach einigen wenigen Schritten einen Ausgleich erzielt werden. Es wird außerdem gezeigt, daß ein dezentralisierte verwalteter Kookkurrenzgraph als Grundlage für eine vollstän-dig integrierte, dezentrale Suchmaschine verwendet werden kann; ein Prototyp hierzu, der im heutigen World Wide Web funktioniert und verwendet werden kann, wird entworfen, implementiert und experimentell evaluiert. Diese Suchmaschine verwendet Textzentroide, um zu Suchanfragen und Nutzerinteressen passende Dokumente zu finden.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved