Flight over Bristol

Bristol Algorithms Days 2010
Feasibility Workshop

15 - 16 February 2010

  •    •    •  

Can One Index for Searching with Errors?

Moshe Lewenstein

Indexing of full-texts plays an important role in many real-life systems and has been central to research in the pattern matching field for close to 40 years. Well known data structures have been constructed for indexing texts, such as suffix trees and suffix arrays, many uses for indexing (some surprisng) have been discovered, and the relationship beween compression and indexing has been widely explored in the last decade. In parallel, pattern matching with errors has been researched intensively and many different, interesting, efficient methods have been devised to solve this problem. A very natural problem is to index with errors. However, this turns out to be a difficult problem. There has been some initial success but there is a long way to go. I will explore the current state of knowledge in this talk.


  The University of Bristol   EPSRC