ECCC-Report TR15-111https://eccc.weizmann.ac.il/report/2015/111Comments and Revisions published for TR15-111en-usFri, 25 Mar 2016 19:14:31 +0300
Revision 1
| Streaming algorithms for embedding and computing edit distance in the low distance regime |
Elazar Goldenberg,
Michal Koucky,
Diptarka Chakraborty
https://eccc.weizmann.ac.il/report/2015/111#revision1
The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. Whereas, the Hamming distance between $x$ and $y$ is the number of bit flips needed for converting $x$ to $y$.
In this paper we study a randomized injective embedding of the edit distance into the Hamming distance with a small distortion.
We show a randomized embedding with quadratic distortion. Namely, for any $x,y$ satisfying that their edit distance equals $k$, the Hamming distance between the embedding of $x$ and $y$ is $O(k^2)$ with high probability. This improves over the distortion ratio of $O(\log n \log^* n)$ obtained by Jowhari (2012) for small values of $k$. Moreover, the embedding output size is linear in the input size and the embedding can be computed using a single pass over the input.
We provide several applications for this embedding. Among our results we provide a one-pass (streaming) algorithm for edit distance running in space $O(s)$ and computing edit distance exactly up-to distance $s^{1/6}$. This algorithm is based on {\em kernelization} for edit distance that is of independent interest.
In this paper we study a randomized injective embedding of the edit distance into the Hamming distance with a small distortion. This question was studied by Jowhari (ESA 2012) and is mainly motivated by two questions in communication complexity: the document exchange problem and deciding edit distance using a
sketching protocol.
We show a randomized embedding with quadratic distortion. Namely, for any $x,y$ satisfying that their edit distance equals $k$, the Hamming distance between the embedding of $x$ and $y$ is $O(k^2)$ with high probability. This improves over the distortion ratio of $O(\log n \log^* n)$ obtained by Jowhari for small values of $k$. Moreover, the embedding output size is linear in the input size and
the embedding can be computed using a single pass over the input.
Fri, 25 Mar 2016 19:14:31 +0300https://eccc.weizmann.ac.il/report/2015/111#revision1
Paper TR15-111
| Low Distortion Embedding from Edit to Hamming Distance using Coupling |
Elazar Goldenberg,
Michal Koucky,
Diptarka Chakraborty
https://eccc.weizmann.ac.il/report/2015/111
The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. Whereas, the Hamming distance between $x$ and $y$ is the number of bit flips needed for converting $x$ to $y$.
In this paper we study a randomized injective embedding of the edit distance into the Hamming distance with a small distortion. This question was studied by Jowhari (ESA 2012) and is mainly motivated by two questions in communication complexity: the document exchange problem and deciding edit distance using a
sketching protocol.
We show a randomized embedding with quadratic distortion. Namely, for any $x,y$ satisfying that their edit distance equals $k$, the Hamming distance between the embedding of $x$ and $y$ is $O(k^2)$ with high probability. This improves over the distortion ratio of $O(\log n \log^* n)$ obtained by Jowhari for small values of $k$. Moreover, the embedding output size is linear in the input size and
the embedding can be computed using a single pass over the input.
Wed, 08 Jul 2015 16:37:33 +0300https://eccc.weizmann.ac.il/report/2015/111