Exact and Approximate Pattern Matching in the Streaming Model

DOI10.1109/FOCS.2009.11zbMath1292.68174OpenAlexW2164259467MaRDI QIDQ5171182

Ely Porat, Benny Porat

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.11

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Dictionary Matching in a Stream, On pattern matching with \(k\) mismatches and few don't cares, Fingerprints in compressed strings, Simple real-time constant-space string matching, Space lower bounds for online pattern matching, Longest common substring with approximately \(k\) mismatches, Time-space trade-offs for Lempel-Ziv compressed indexing, Unnamed Item, Unnamed Item, Unnamed Item, A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance, On string matching with mismatches, Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams, String Matching: Communication, Circuits, and Learning., Fingerprints for highly similar streams, Streaming pattern matching with \(d\) wildcards, Real-Time Streaming String-Matching, Simple Real-Time Constant-Space String Matching, Space Lower Bounds for Online Pattern Matching, Periodicity in data streams with wildcards, Low-weight superimposed codes and related combinatorial structures: bounds and applications, Circular pattern matching with \(k\) mismatches, Streaming \(k\)-mismatch with error correcting and applications, Periodicity and Cyclic Shifts via Linear Sketches, Streaming Dictionary Matching with Mismatches, Searching Long Repeats in Streams, Quasi-Periodicity in Streams, Unnamed Item, Tight tradeoffs for real-time approximation of longest palindromes in streams, Real-Time Streaming Multi-Pattern Search for Constant Alphabet, Recent advances in text-to-pattern distance algorithms, Computing the maximum exponent in a stream, Streaming dictionary matching with mismatches