Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams
From MaRDI portal
Publication:5002743
DOI10.4230/LIPIcs.ICALP.2018.65zbMath1499.68424OpenAlexW2885605070MaRDI QIDQ5002743
Shay Golan, Tsvi Kopelowitz, Ely Porat
Publication date: 28 July 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.65
Data structures (68P05) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)
Related Items (5)
Unnamed Item ⋮ Streaming \(k\)-mismatch with error correcting and applications ⋮ Streaming Dictionary Matching with Mismatches ⋮ Searching Long Repeats in Streams ⋮ Streaming dictionary matching with mismatches
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple real-time constant-space string matching
- The communication complexity of the Hamming distance problem
- Simple deterministic wildcard matching
- Pattern matching with don't cares and few errors
- Parameterized matching on non-linear structures
- Efficient string matching with k mismatches
- The space complexity of approximating the frequency moments
- Alphabet dependence in parameterized matching
- Approximate swapped matching.
- Parameterized pattern matching: Algorithms and applications
- Dictionary matching with a few gaps
- Swap and mismatch edit distance
- Generalized function matching
- Pattern Matching in Multiple Streams
- Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications
- Dictionary Matching in a Stream
- Improved Sketching of Hamming Distance with Error Correcting
- Verifying candidate matches in sparse and wildcard matching
- Approximate parameterized matching
- Periodicity in Streams
- Efficient randomized pattern-matching algorithms
- Efficient string matching
- Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance
- Pattern Matching with Swaps
- Approximate Hamming Distance in a Stream
- Streaming Pattern Matching with d Wildcards
- Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
- Faster algorithms for string matching with k mismatches
- Real-Time Streaming String-Matching
- Communication and Streaming Complexity of Approximate Pattern Matching
- Real-Time Streaming Multi-Pattern Search for Constant Alphabet
- Dictionary Matching with One Gap
- An Improved Query Time for Succinct Dynamic Dictionary Matching
- Exact and Approximate Pattern Matching in the Streaming Model
- Explicit Nonadaptive Combinatorial Group Testing Schemes
- ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk
- A Framework for Dynamic Parameterized Dictionary Matching
- Succinct Online Dictionary Matching with Improved Worst-Case Guarantees.
- Function Matching
This page was built for publication: Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams
