Top-k aggregation queries in large-scale distributed systems
Sebastian Michel · Max Planck Institute for Plasma Physics · 2007
Distributed top-k query processing has recently become an essential functionality in a large number of emerging application classes like Internet traffic monitoring and Peer-to-Peer Web search. This work addresses efficient algorithms for distributed top-k queries in wide-area networks where the index lists for the attribute values (or text terms) of a query are distributed across a number of data peers. More precisely, in this thesis, we make the following distributions: We present the family of KLEE algorithms that are a fundamental building-block towards efficient top-k query processing in distributed systems. We present means to model score distributions and show how these score models can be used to reason about parameter values that play an important role in the overall performance of KLEE. We present GRASS, a family of novel algorithms based on three optimization techniques significantly increased overall performance of KLEE and related algorithms. We present probabilistic guarantees for the result quality. Moreover, we present Minerva1, a distributed search engine. Minerva offers a highly distributed (in both the data dimension and the computational dimension), scalable, and efficient solution toward the development of internet-scale search engines. Top-k Anfragen spielen eine grose Rolle in einer Vielzahl von Anwendungen, insbesondere im Bereich von Informationssystemen, bei denen eine kleine, sorgfaltig ausgewahlte Teilmenge der Ergebnisse den Benutzern prasentiert werden soll. Beispiele hierfur sind Suchmaschinen wie Google, Yahoo oder MSN. Obwohl die Forschung in diesem Bereich in den letzten Jahren grose Fortschritte gemacht hat, haben Top-k-Anfragen in verteilten Systemen, bei denen die Daten auf verschiedenen Rechnern verteilt sind, vergleichsweise wenig Aufmerksamkeit erlangt. In dieser Arbeit beschaftigen wir uns mit der effizienten Verarbeitung eben dieser Anfragen. Die Hauptbeitrage gliedern sich wie folgt. Wir prasentieren KLEE, eine Familie neuartiger Top-k-Algorithmen. Wir entwickeln Modelle mit denen Datenverteilungen beschrieben werden konnen. Diese Modelle sind die Grundlage fur eine Schatzung diverser Parameter, die einen grosen Einfluss auf die Performanz von KLEE und anderen ahnlichen Algorithmen haben. Wir prasentieren GRASS, eine Familie von Algorithmen, basierend auf drei neuartigen Optimierungstechniken, mit denen die Performanz von KLEE und ahnlichen Algorithmen verbessert wird. Wir prasentieren probabilistische Garantien fur die Ergebnisgute. Wir prasentieren Minerva, eine neuartige verteilte Peer-to-Peer-Suchmaschine.