Sketches and streaming algorithms for string processing
1 : École normale supérieure, Paris
École normale supérieure, Paris
The streaming model of computation is a particularly strict model, where we assume that the input arrives one data item at a time, and must account for all the space used by the algorithm, including the space used to store the input. Surprisingly, in the seminal paper at FOCS 2009, Porat and Porat showed that one can find all occurrences of a pattern of length m in a streaming text in O(log m) space (compare to the classical algorithms that require linear space). The main tool used by the algorithm is sketching, lossy compressed representation of the data. In this talk, we will review recent breakthroughs in the field of streaming pattern matching, including sketches and streaming algorithms for dictionary matching and approximate pattern matching under Hamming and edit distances.
- Poster