Journées Nationales Informatique Mathématique 2019
11-14 mars 2019 Orléans (France)
Sketches and streaming algorithms for string processing
Tatiana Starikovskaya  1  
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
Personnes connectées : 1