Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance

In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance problem, we give a greedy algorithm that distinguishes in time $\tilde{\mathcal{O}}(\frac{n}{k}+k^{2})$ between length-n input strings with edit distance at most $k$ and those with edit distance more than $4k^{2}$. This is an improvement and a simplification upon the main result of [Goldenberg, Krauthgamer, Saha, FOCS 2019], where the $k$ vs $\Theta(k^{2})$ gap edit distance problem is solved in $\tilde{\mathcal{O}}(\frac{n}{k}+k^{3})$ time. We further generalize our result to solve the $k$ vs $\alpha k$ gap edit distance problem in time $\tilde{\mathcal{O}}(\frac{n}{\alpha}+k^{2}+\frac{k}{\alpha}\sqrt{nk})$, strictly improving upon the previously known bound $\tilde{\mathcal{O}}(\frac{n}{\alpha}+k^{3})$. Finally, we show that if the input strings do not have long highly periodic substrings, then the gap edit distance problem can be solved in sublinear time within any factor $\alpha > 1$. Specifically, if the strings contain no substring of length $\ell$ with the shortest period of length at most $2k$, then the $k$ vs $(1+\varepsilon)k$ gap edit distance problem can be solved in time $\tilde{\mathcal{O}}(\frac{n}{\varepsilon^{2}k}+k^{2}\ell)$. We further give the first sublinear-time algorithm for the probabilistic embedding of edit distance to Hamming distance. Our $\tilde{\mathcal{O}}(\frac{n}{p})$ -time procedure yields an embedding with distortion $k^{2}p$, where $k$ is the edit distance of the original strings. Specifically, the Hamming distance of the resultant strings is between $\frac{k-p+1}{p}$ and $k^{2}$ with good probability. This generalizes the linear-time embedding of [Chakraborty, Goldenberg, Koucký, STOC 2016], where the resultant Hamming distance is between $k$ and $k^{2}$. Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.

Authors

• Tomasz Kociumaka
• Barna Saha

Keywords

• Hamming distance
• Approximation algorithms
• Heuristic algorithms
• Time complexity
• Probabilistic logic
• Measurement
• Distortion
• Edit Distance
• Sublinear-time Algorithms
• Random Walk
• Linear Time
• Problem In Time
• Input String
• Good Probability
• Running Time
• Classification Algorithms
• Iterative Algorithm
• Text Data
• Total Run Time
• Fast Algorithm
• Mahalanobis Distance
• Quadratic Problem
• Exact Algorithm
• Positional Candidate
• Binary Search
• Number Of Edits
• Number Of Deletions
• sublinear algorithms
• embedding