Approximating Text-to-Pattern Distance via Dimensionality Reduction

2020/02/09 by Uznański, Przemysław
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2002.03459

Abstract

Text-to-pattern distance is a fundamental problem in string matching, where given a pattern of length m and a text of length n, over an integer alphabet, we are asked to compute the distance between pattern and the text at every location. The distance function can be e.g. Hamming distance or ℓ_p distance for some parameter p > 0. Almost all state-of-the-art exact and approximate algorithms developed in the past ∼ 40 years were using FFT as a black-box. In this work we present \widetildeO(n/ε²) time algorithms for (1±ε)-approximation of ℓ₂ distances, and \widetildeO(n/ε³) algorithm for approximation of Hamming and ℓ₁ distances, all without use of FFT. This is independent to the very recent development by Chan et al. [STOC 2020], where O(n/ε²) algorithm for Hamming distances not using FFT was presented -- although their algorithm is much more "combinatorial", our techniques apply to other norms than Hamming.

Related

• Approximating Text-to-Pattern Hamming Distances
• Faster Approximate(d) Text-to-Pattern L1 Distance
• Approximating Approximate Pattern Matching
• Faster Algorithms for Text-to-Pattern Hamming Distances
• Breaking the Variance: Approximating the Hamming Distance in O(1/ε) Time Per Alignment