SPP 1307 Home Related Work Goals References Source code and tools Test instances: Texts Test instances: Patterns

Practical Approximate Pattern Matching with Index Structures

Project

In this research project we apply the whole spectrum of algorithm engineering to index structures for approximate pattern matching. In contrast to the case of exact searching there is a big gap between theory and practice for the approximate case. We want to close this gap with our project. Some of the approaches which yield theoretical advances, seem to be not applicable in practice due to big constants.

A library of pattern matching algorithms would be of great benefit for other researches and computer scientists, providing efficient methods for index-based approximate pattern matching. The library is supposed to be an interface for the ongoing progress in the field of indexes and algorithms. The implementations form a working basis for the further algorithm engineering process, but as well can be used by e.g. biologists to solve real world problems, like analyzing biological data. The library is supposed to offer index structures and search algorithms, developed and optimized espacially considering the following aspects:

Efficient applicability to for big, real world problem instances, while using general and flexible error models.
Index structures and search algorithms in secondary memory.
Distributed index structures and search algorithms.
Cache-efficient search algorithms.