Please use this identifier to cite or link to this item:
doi:10.22028/D291-25870
Title: | Adaptive Suchverfahren |
Author(s): | Schulz, Frank |
Language: | German |
Year of Publication: | 1999 |
SWD key words: | Suchverfahren Markov-Kette Online-Algorithmus Listenverarbeitung |
Free key words: | adaptiver Suchalgorithmus adaptive search algorithm Markovian request sequence |
DDC notations: | 004 Computer science, internet |
Publikation type: | Dissertation |
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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-11950 hdl:20.500.11880/25926 http://dx.doi.org/10.22028/D291-25870 |
Advisor: | Hotz, Günter |
Date of oral examination: | 29-Oct-1999 |
Date of registration: | 24-Jul-2007 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
Dissertation_967_Schu_Fran_1999.pdf | 1,5 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.