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, die wir zur Datenkompression einsetzen. Außerdem schlagen wir eine Verallgemeinerung des Kostenmaßes für Kodes und Suchbäume vor, bei dem die Vergleichskosten nicht konstant sind, sondern exponentiell mit der Tiefe wachsen, und analysieren die Auswirkungen dieses Modells.
We consider the online list accessing problem and present a new family of competitive-optimal deterministic list update algorithms which is the largest class of such algorithms known to-date. This family, called {\sc Sort-by-Rank} ({\sc sbr}), is parametrized with a real $0 \leq \alpha \leq 1$, where {\sc sbr}(0) is the {\sc Move-to-Front} algorithm and {\sc sbr}(1) is equivalent to the {\sc Timestamp} algorithm. The behaviour of {\sc sbr}($\alpha$) mediates between the eager strategy of {\sc Move-to-Front} and the more conservative behaviour of {\sc Timestamp}. We also present a family of algorithms {\sc Sort-by-Delay} ({\sc sbd}) which is parametrized by the positive integers, where {\sc sbd}(1) is {\sc Move-to-Front} and {\sc sbd}(2) is equivalent to {\sc Timestamp}. In general, {\sc sbd}($k$) is $k$-competitive for $k \geq 2$. This is the first class of algorithms that is asymptotically optimal for independent, identically distributed requests while each algorithm is constant-competitive. Empirical studies with with both generated and real-world data are also included.
We consider problem sources as information sources. The concepts of statistical information theory are applied to construct efficient algorithms and to obtain lower bounds for the average case running times. We examine sorting and give an algorithm that sorts $t$ symbols from an ordered alphabet ${\cal A}$ in time $O(H({\cal A}) \cdot t)$, where $H({\cal A})$ is the entropy of the source which is assumed to be memoryless or Markovian. Furthermore we consider the convex hull problem in the plane. Two algorithms are given, one of them constructs the convex hull of $t$ points in expected time $\leq 9 \cdot t$, where only very general assumptions about the point distribution are made. }
We consider self-organizing data structures in the case where the sequence of accesses can be modeled by a first order Markov chain. For the simple-k- and batched-k--move-to-front schemes, explicit formulae for the expected search costs are derived and compared. We use a new approach that employs the technique of expanding a Markov chain. This approach generalizes the results of Gonnet/Munro/Suwanda. In order to analyze arbitrary memory-free move-forward heuristics for linear lists, we restrict our attention to a special access sequence, thereby reducing the state space of the chain governing the behaviour of the data structure. In the case of accesses with locality (inert transition behaviour), we find that the hierarchies of self-organizing data structures with respect to the expected search time are reversed, compared with independent accesses. Finally we look at self-organizing binary trees with the move-to-root rule and compare the expected search cost with the entropy of the Markov chain of accesses.
Wir betrachten das Wörterbuchproblem, wenn die Folge der Suchanfragen durch eine Markov-Kette modelliert werden kann (Anfragequelle mit Gedächtnis). Selbst-organisierende Datenstrukturen stellen eine Möglichkeit zur Behandlung dar, und erlauben die dynamische Anpassung an das Zugriffsverhalten. Für die Simple-k- und Batched-k-Nach-Vorne-Schieben- Regel werden Formeln für die erwartete Suchzeit hergeleitet. Es stellt sich heraus, daß bei abhängigen Zugriffen mit trägem Übergangsverhalten (Lokalität der Zugriffe) die Hierarchie der Heuristiken bzgl. der erwarteten Suchzeit genau umgedreht ist als bei unabhängigen Zugriffen. Weiter betrachten wir eine spezielle Folge abhängiger Zugriffe, um die Größe des Zustandsraums der Datenstruktur zu reduzieren. In diesem Fall können wir beliebige Vorwärts-Regeln miteinander vergleichen und stellen auch hier fest, daß die Rangfolge der Regeln genau umgekehrt ist, verglichen mit unabhängigen Zugriffen. Außerdem betrachten wir selbst-organisierende Suchbäume mit der Zur-Wurzel-Rotieren-Regel. Bei beliebiger vorgegebener stationärer Verteilung können Zugriffsfolgen mit Lokalität angegeben werden, so daß die erwartete Suchzeit beliebig nahe an 1 liegt.