Adaptive Suchverfahren

Abstract

In der vorliegenden Arbeit untersuchen wir adaptive Suchalgorithmen. Diese Verfahren arbeiten online und versuchen, ohne Kenntnis zukünftiger Anfragen gute Antwortzeiten zu erzielen, indem sie ihre Suchstrategie dynamisch ändern. Wir analysieren bekannte und entwickeln neue Verfahren für sequentielle Suche unter kompetitiven und stochastischen Kostenmodellen. Ein Schwerpunkt der Arbeit liegt auf Markov-Ketten als Zugriffsmodell, die eine Verallgemeinerung unabhängiger Zugriffe darstellen und praktisch beobachtete Phänomene gut beschreiben können. Verschiedene Varianten des Problems wie randomisierte Algorithmen, gewichtete Zugriffskosten oder bidirektionale Suche werden ebenfalls betrachtet, außerdem vergleichen wir die Konvergenzgeschwindigkeit der einzelnen Verfahren. Adaptive Verfahren ermöglichen es implizit, statistische Informationen über die Anfragefolgen zu sammeln, diewir zur Datenkompression einsetzen. Außerdemschlagen wir eine Verallgemeinerung des Kostenmaßes für Kodes und Suchbäume vor, bei demdie Vergleichskosten nicht konstant sind, sondern exponentiellmit der Tiefe wachsen, und analysieren die Auswirkungen dieses Modells.

This thesis deals with adaptive search algorithms. These algorithms work online and strive to achieve fast response time without knowledge of future requests by modifying their search strategy dynamically. We analyse known and devise new algorithms for sequential search problems in the competitive and average case settings. Special emphasis is placed on Markovian request sequences, as they provide a generalization of the independent request model and are well suited to describe real data. We also consider several variations of the problem, like randomised algorithms, weighted access costs or bidirectional search, and we investigate the convergence speeds of thealgorithms. Adaptive algorithms implicitly collect statistical information on the request sequence that can be used for data compression. Furthermore we propose a generalization of the cost functions on codes and trees. While the comparison costs are constant in the standard model, they now increase exponentially with the depth. We analyse and discuss the impacts of this model.