»Search Algorithms«

Christian Schindelhauer

Contents

We explore the many facets and variants of search algorithms in Computer Science.

We start with the simple text search problem and discuss the automata based search algorithm of Knuth, Morris and Pratt. Then, we deepen our investigations to the field of pattern matching.

Further we discuss the field of search in large data sets using semantic information. This is the area of information retrieval. We give an overview on techniques used in data mining and conclude this section with efficient algorithms for learning pattern languages in algorithmic learning theory.

The World-Wide-Web is a nearly endless source of information. However searching the web is a difficult task, because of its ever increasing size. The main difficulty is to find relevant documents. A common technique to measure the importance of web documents, is to analyse the link structure fo the Web. We present how search engines tackle this problem by the use of Markov processes.

In computational geometry finding the next neighbor in Euclidean space can be time-consuming. Therefore approximate solutions are also welcome, since for this problem more efficient algorithms are known. In this context we discuss several search algorithms of computation geometry.

Besides these search problems we discuss space-time tradeoffs for search algorithms in computational complexity, the aspects of search algorithm for search the DNS, and algorithms for finding optimal solutions in linear programming systems.