Approximating Approximate Pattern Matching

DOI10.4230/LIPICS.CPM.2019.15MaRDI QIDQ5088905zbMATH OpenOpenAlexFDO

Authors Jan Studený, Przemysław Uznański

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1810.01676

zbMATH Keywords

\(\ell_1\) distance\(\ell_p\) distanceapproximate pattern matchingapproximation algorithmsHamming distance

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Approximating general metric distances between a pattern and a text
• Combinatorial Pattern Matching
• Recent advances in text-to-pattern distance algorithms

Cites work

• \(L_{1}\) pattern matching lower bound
• A simple algorithm for approximating the text-to-pattern Hamming distance
• A subquadratic approximation scheme for partition
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Approximating general metric distances between a pattern and a text
• Brief announcement: Hamming distance completeness and sparse matrix multiplication
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Fast algorithms for approximately counting mismatches
• Faster algorithms for string matching with k mismatches
• Generalized String Matching
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• On the exact space complexity of sketching and streaming small norms
• Optimal space lower bounds for all frequency moments
• Taylor polynomial estimator for estimating frequency moments
• The \(k\)-mismatch problem revisited
• The one-way communication complexity of Hamming distance
• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• Univariate stable distributions. Models for heavy tailed data

Cited in

(15)

• Improved approximate pattern matching on hypertext
• On matching generalised repetitive patterns
• Dynamic and approximate pattern matching in 2D
• Recent advances in text-to-pattern distance algorithms
• Approximate pattern matching on elastic-degenerate text
• Deterministic Sampling–A New Technique for Fast Pattern Matching
• Extracting Approximate Patterns
• A Subquadratic Algorithm for Approximate Regular Expression Matching
• The Negligible and Yet Subtle Cost of Pattern Matching
• Communication and Streaming Complexity of Approximate Pattern Matching
• A Linear Size Index for Approximate Pattern Matching
• scientific article; zbMATH DE number 7758337 (Why is no real title available?)
• scientific article; zbMATH DE number 7756108 (Why is no real title available?)
• Approximate input sensitive algorithms for point pattern matching
• Pattern matching with pair correlation distance

This page was built for publication: Approximating Approximate Pattern Matching

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