Cooperatively Managing and Exploiting Distributed Co-occurrence Graphs

Zusammenfassung

The property of terms to occur adjacently in text corpora can be expressed by co-occurrence graphs. Such data structures proved to be useful tools for extracting semantic information in natural language processing. When communities work collaboratively on joint documents, 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. Moreover, a local co-occurrence graph in each peer is built from documents of the users attached to the peer and obtained from elsewhere. 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. 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....