Exact and Approximate Pattern Matching in the Streaming Model

DOI10.1109/FOCS.2009.11MaRDI QIDQ5171182zbMATH OpenOpenAlexFDO

Authors Benny Porat, Ely 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)

Cited in

(34)

• Time-space trade-offs for Lempel-Ziv compressed indexing
• On string matching with mismatches
• Streaming pattern matching with \(d\) wildcards
• Recent advances in text-to-pattern distance algorithms
• Computing the maximum exponent in a stream
• Streaming dictionary matching with mismatches
• Low-weight superimposed codes and related combinatorial structures: bounds and applications
• Streaming \(k\)-mismatch with error correcting and applications
• Tight tradeoffs for real-time approximation of longest palindromes in streams
• Longest common substring with approximately \(k\) mismatches
• Real-time streaming string-matching
• Simple real-time constant-space string matching
• Space Lower Bounds for Online Pattern Matching
• Periodicity and cyclic shifts via linear sketches
• On pattern matching with \(k\) mismatches and few don't cares
• Dictionary matching in a stream
• Simple real-time constant-space string matching
• Space lower bounds for online pattern matching
• Fingerprints for highly similar streams
• Streaming periodicity with mismatches
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Streaming Dictionary Matching with Mismatches
• Quasi-Periodicity in Streams
• Searching Long Repeats in Streams
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Streaming for aibohphobes: longest palindrome with mismatches
• A simple algorithm for approximating the text-to-pattern Hamming distance
• String Matching: Communication, Circuits, and Learning.
• Circular pattern matching with \(k\) mismatches
• scientific article; zbMATH DE number 7758337 (Why is no real title available?)
• scientific article; zbMATH DE number 7758348 (Why is no real title available?)
• Locally consistent parsing for text indexing in small space
• Substring complexity in sublinear space
• Regular languages in the sliding window model

This page was built for publication: Exact and Approximate Pattern Matching in the Streaming Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5171182)