Flight over Bristol

Bristol Algorithms Days 2010
Feasibility Workshop

15 - 16 February 2010

  •    •    •  

Pattern Matching in Streaming Data

Raphaël Clifford & Benjamin Sach

Many sophisticated methods have been developed for pattern matching under a variety of measures of distance over recent years. However, almost without exception these have been analysed in models of computation where it is assumed that all of the data can be accessed at any time. We consider the problem of pattern matching in streaming data where symbols arrive one at a time and at great speed. Here, not only is there a restriction on the storage space available but we also require any new matches that are found to be reported as soon as they occur. We will discuss recent results and the degree to which the gap between the running time of the best online and offline algorithms can be closed.


  The University of Bristol   EPSRC