Recent advances in text-to-pattern distance algorithms

DOI10.1007/978-3-030-51466-2_32OpenAlexW3037883011MaRDI QIDQ2106622FDOQ2106622

Authors: Przemysław Uznański 

Publication date: 16 December 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-51466-2_32

Recommendations

• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• Approximating Approximate Pattern Matching
• A simple algorithm for approximating the text-to-pattern Hamming distance
• Approximating general metric distances between a pattern and a text
• Pattern matching with pair correlation distance

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Fast algorithms for approximately counting mismatches
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Generalized String Matching
• Faster algorithms for string matching with k mismatches
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Title not available (Why is that?)
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• The \(k\)-mismatch problem revisited
• Exact and Approximate Pattern Matching in the Streaming Model
• Approximate matching in the \(L_{\infty }\) metric
• \(L_{1}\) pattern matching lower bound
• Efficient string matching with k mismatches
• The one-way communication complexity of Hamming distance
• Approximating general metric distances between a pattern and a text
• Optimal space lower bounds for all frequency moments
• Pattern matching in the Hamming distance with thresholds
• On approximate pattern matching with thresholds
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Approximating Approximate Pattern Matching
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Hamming Distance Completeness
• Efficient matching of nonrectangular shapes.
• Approximating text-to-pattern Hamming distances
• A simple algorithm for approximating the text-to-pattern Hamming distance
• The streaming \(k\)-mismatch problem
• Improved range-summable random variable construction algorithms
• Approximate Hamming distance in a stream
• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• Approximating Text-To-Pattern Distance via Dimensionality Reduction

Cited In (1)

• Approximating Approximate Pattern Matching

This page was built for publication: Recent advances in text-to-pattern distance algorithms

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