Abstracts

• Frank Schulz. Adaptive Suchverfahren. Dissertation, Universität des Saarlandes, Oktober 1999. (Gzipped PostScript, 176 pages, 632352 bytes)

  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.

• Frank Schulz. Two New Families of Self-Organizing Data Structures. In ISAAC'98, LNCS 1533, pages 99-108, December 1998. (Gzipped PostScript, 10 pages, 74276 bytes)

  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.

• Günter Hotz und Frank Schulz. Sorting and searching in view of the noiseless coding theorem. Manuskript, 1997. (Gzipped PostScript, 10 pages, 100802 bytes)

  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. }

• Frank Schulz and Elmar Schömer. Self-organizing data structures with dependent accesses. In ICALP'96, LNCS 1099, pages 526-537, July 1996. (Gzipped PostScript, 12 pages, 58262 bytes)

  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.

• Frank Schulz. Selbst-organisierende Datenstrukturen bei abhängigen Zugriffen. Diplomarbeit, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, September 1995. (Gzipped PostScript, 106 pages, 237161 bytes)

  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.