Optimized information discovery in structured peer-to-peer overlay networks

Abstract

Peer-to-peer (P2P) overlay networks allow for efficient information discovery in large-scale distributed systems. Although point queries are well supported by current P2P systems - in particular systems based on distributed hash tables (DHTs) -, providing efficient support for more complex queries remains a challenge. Therefore, the goal of this research is to develop methodologies that enable efficient processing of complex queries, in particular processing of multi-attribute range queries, over DHTs.

Generally, the support for multi-attribute range queries over DHTs has been provided either by creating an individual index for each data attribute or by creating a single index using the combination of all data attributes. In contrast to these approaches, we propose to create and modify indices using the attribute combinations that dynamically appear in multi-attribute range queries in the system.

In order to limit the overhead induced by index maintenance, the total number of created indices has to be limited. Thus, one of the major problems is to create a limited number of indices such that the overall system performance is optimal for multi-attribute range queries. We propose several index recommendation algorithms that implement heuristic solutions to this NP-hard problem. Our evaluations show that these heuristics lead to a close-to-optimal system performance for multi-attribute range queries.

The final outcome of this research is an adaptive DHT-based information discovery system that adapts its set of indices according to the dynamic load of multi-attribute range queries in the system. The index adaptation is carried out using a four-phase index adaptation process. Our evaluations show that the adaptive information discovery system continuously optimizes the overall system performance for multi-attribute range queries. Moreover, compared to a non-adaptive system, our system achieves several orders of a magnitude improved performance.

Peer-to-Peer-Netze ermöglichen die effiziente Suche nach Informationen in großen verteilten Systemen. Obwohl einfache Anfragen nach einzelnen Werten bereits gut durch aktuelle Peer-to-Peer-Systeme unterstützt werden - insbesondere Systeme basierend auf verteilten Hash-Tabellen (engl. Distributed Hash Table; DHT) -, so ist die Unterstützung komplexer Anfragen eine offene Frage. Das Ziel dieser Dissertation ist daher der Entwurf und die Umsetzung von Methoden, welche eine effiziente Verarbeitung komplexer Anfragen, insbesondere von Multiattributsbereichsanfragen, mit Hilfe von DHTs ermöglichen.

Im Allgemeinen werden Multiattributsbereichsanfragen auf Basis von DHTs entweder durch die Erstellung individueller Indizes für jedes einzelne Attribut realisiert, oder durch die Erstellung eines einzelnen Index über alle Attribute. Im Gegensatz zu diesen Ansätzen wird in dieser Dissertation vorgeschlagen, Indizes auf Grundlage der dynamischen Attributkombinationen zur erzeugen und anzupassen, welche tatsächlich in Bereichsanfragen verwendet werden.

Um den Aufwand der Indexverwaltung zu reduzieren, muss die Anzahl der ausgewählten Indizes beschränkt werden. Eines der wesentlichen Probleme ist daher die Erstellung einer begrenzen Anzahl von Indizes, so dass die optimale Systemleistung für die gegebenen Bereichsanfragen erzielt wird. Hierfür werden verschiedene Algorithmen zur Auswahl von Indizes vorgeschlagen. Aufgrund der Tatsache, dass es sich bei der optimalen Auswahl um ein NP-hartes Problem handelt, handelt es sich hierbei um heuristische Lösungen. Die Evaluierung dieser Ansätze zeigt, dass hierdurch eine nahezu optimale Leistung für Multiattributsbereichsanfragen erzielt wird.

Der Hauptbeitrag dieser Dissertation ist somit ein adaptives DHT-basiertes System zur Informationssuche, welches die Menge der Indizes aufgrund der dynamischen Anfragelast adaptiert. Die Indexadaption wird dabei als ein vierstufiger Prozess implementiert. Die Evaluierungen belegen, dass das vorgeschlagene System Multiattributsbereichsanfragen effektiv optimiert. Im Vergleich zu einem nicht adaptiven System wird die Leistung dabei um mehrere Größenordnungen verbessert.