Neural Embeddings for Nearest Neighbor Search Under Edit Distance
Year: 2019

Abstract:
The edit distance between two sequences is an important metric with many applications. The drawback, however, is the high computational cost of many basic problems involving this notion, such as the nearest neighbor search. A natural approach to overcoming this issue is to embed the sequences into a vector space such that the geometric distance in the target space approximates the edit distance in the original space. However, the known edit distance embedding algorithms, such as Chakraborty et al. (2016), construct embeddings that are data-independent, i.e., do not exploit any structure of embedded sets of strings. In this paper we propose an alternative approach, which learns the embedding function according to the data distribution. Our experiments show that the new algorithm has much better empirical performance than prior data-independent methods.

text: The edit distance between two sequences is an important metric with many applications. The drawback, however, is the high computational cost of many basic problems involving this notion, such as the nearest neighbor search. A natural approach to overcoming this issue is to embed the sequences into a vector space such that the geometric distance in the target space approximates the edit distance in the original space. However, the known edit distance embedding algorithms, such as Chakraborty et al. (2016), construct embeddings that are data-independent, i.e., do not exploit any structure of embedded sets of strings. In this paper we propose an alternative approach, which learns the embedding function according to the data distribution. Our experiments show that the new algorithm has much better empirical performance than prior data-independent methods.

heading: 1 Introduction
text: The edit distance is a popular metric for computing the dissimilarity between two strings. Given strings x and y, the edit distance dE(x, y) between them is equal to the minimum number of character insertions, deletions and substitutions needed to transform x into y. The metric and its many variants have been defined and studied since the 1960s (Levenshtein, 1966; Wagner and Fischer, 1974). It has found many applications in computational biology (to measure the similarity between DNA/RNA sequences), natural language processing, information theory and other fields.
From the algorithmic perspective, the main drawback of edit distance is its computational complexity. The best known algorithm for computing the distance between two strings of length n takes time that is roughly quadratic in n (Masek and Paterson, 1980); there is also evidence that this runtime is essentially optimal (Backurs and Indyk, 2015). Furthermore, many applications require finding the closest string in a large collection of (say) N strings. Thus, even if we could estimate the edit distance in time O(n), computing the distances to all strings in the collection would take O(Nn) time, which is infeasible for large data sets.
A natural approach to resolving both issues relies on low-distortion embeddings. The idea is to construct a mapping f that maps strings into a d-dimensional space <d, such that the edit distance dE(x, y) is approximated by the distance ‖f(x) − f(y)‖ between the images of the strings, up to some factor D called distortion. If the mapping f can be evaluated efficiently, this immediately implies an efficient way to compute the edit distance. Furthermore, embedding strings into space equipped with a norm ‖ · ‖ makes it possible to use nearest neighbor search algorithms designed for that norm. For many normed spaces, e.g. Minkowski norms `dp, many efficient approximate nearest neighbor search algorithms are available. This dual goal has motivated a long line of research focused on designing efficient low-distortion embeddings of variants of edit distance into normed spaces (Muthukrishnan and Sahinalp, 2000; Cormode et al., 2001; Ostrovsky and Rabani, 2005; Batu et al., 2006; Jowhari, 2012; Andoni and Onak, 2012; Chakraborty et al., 2016). The method given in the last paper (Chakraborty et al., 2016) was shown to yield good results in practice, in the context of large scale similarity joins, i.e., identifying all pairs of similar sequences (Zhang and Zhang, 2017).
A weakness of the aforementioned algorithms is that they are data-independent, i.e., they do not exploit any structure of embedded sets of strings. In contrast, over the last decade, a large body of research on “learning to hash” showed that data-dependent methods often yield (binary) embeddings with a significantly lower distortion than their data-independent counterparts (Wang et al., 2018). Such methods, however, are typically tailored to obtaining binary representations of vectors that already live in a geometric (typically Hilbert) space. It is thus natural to investigate whether similar benefits of data-dependent methods can be obtained for edit distance embeddings as well.
In this paper we investigate whether the “learning to hash” approach can yield lower distortion embeddings than those obtained using data-independent methods. Since our goal is to obtain distance-preserving mappings of sequences, we use Recurrent Neural Networks as a model implementing those mappings. Specifically, we leverage a two-layer GRU network, depicted in Figure 2 and described in more details in Section 4. The network inputs a sequence of characters (e.g., A, G, T or C for DNA sequences), and outputs a vector of symbols, such that the distance between the vectors approximates the edit distance between the original sequences.
The standard loss function for optimizing the network is the triplet loss (see Figure 1), which has two problems in our scenario. The first problem is distance scaling: triplet loss only controls the relative distance ordering among data points after embedding, rather than the absolute embedding distance between any two data points. This prevents us from getting accurate edit distance estimation from the embedding. To alleviate this issue, we designed a warm-start phase (Phase 1) before optimizing triplet loss (Phase 2), which initializes the embedding so that the discrepancy between the original edit distance and the embedding distance is minimized. The second problem is worst case performance of our model. Due to the nature of learning, the network we learned fits the training data better, and may not do well on unseen hard examples. To alleviate this issue, we append a back up phase (Phase 3), which deals with hard cases.
We emphasize that all the three phases are optimizing the same network. We run Adam algorithm for each phase until convergence, and then use its final state as the initial state for the next phase. Although in principle one may use a single phase with combination of different loss functions to train our model, this requires additional hyperparameter adjustment for the combining ratios. Our current three phase training does not need additional hyperparameters, and therefore can easily fit different scenarios.
The Phase 3 design is non-trivial. Our starting observation is that Recurrent Neural Networks that we employ are not “compatible” with the data-independent mappings of Chakraborty et al. (2016)(which we call CGK from now on). This is because CGK can generate different number of copies for every input character, which is a discrete decision that is hard to be learned by neural networks. We show, however, that this “extra power” of the algorithm is not necessary. In particular, we introduce a “truncated” version of the CGK algorithm (referred to as CGK’), that outputs only 1 or 2 symbols per round. We then show that CGK’ has the same guarantees as the original CGK algorithm. Based on this observation, we design our Phase 3 to be an optimized version of CGK’. Specifically, since each round there will be either 1 or 2 symbols in CGK’, we can directly compare the
two cases and use the difference as approximation to the gradients to train our model. Empirically, Phase 3 does not affect the recall on ordinary datasets much, but greatly improves performance on hard instances.
To evaluate the embeddings, we employ them for nearest neighbor search in a collection of sequences, and compare their performance to CGK. As in Zhang and Zhang (2017) we use three data sets: Gen50ks (containing sequences from the human genome project), UniRef (protein sequence dataset from the UniProt project) and Trec (containing textual information from Medline, an online medical information database). After learning the embeddings, we generate a set of queries, and for each query we identify C sequences in the data set (called candidates) that are closest to the query in the embedded space. We then measure “top-K recall”, i.e., the fraction of the actual top K nearest neighbors (computed using the exact edit distance) returned as one of the C candidates. Our results demonstrate that, over a wide range of parameters K and C, our learned embedding consistently achieves higher recalls than the algorithm of CGK, often by a factor of 3 or more. Similarly, our method often obtains identical recall to that of CGK while using an order of magnitude fewer candidates. This means that in a typical nearest neighbor search “filtering” pipeline, where the candidates are quickly identified in the embedded space and then the exact edit distance is computed between the candidates and queries to identify the final answers, our method reduces the number of exact edit distance computations by up to one order of magnitude. Moreover, our learned embedding also has much more organized structure than CGK, as shown in Appendix A.4.

heading: 2 Related work

heading: 2.1 Edit Distance Computing
text: Exact and approximate algorithms for edit distance computation have been broadly studied, see Navarro (2001) for an overview. For exact algorithms, Wagner and Fischer (1974) gave O(n2)-time algorithm using dynamic programming. This was later improved to O(n2/ log n) by Masek and Paterson (1980). Faster approximation algorithms were studied as well, see e.g., Landau et al. (1998); Batu et al. (2003); Bar-Yossef et al. (2004); Batu et al. (2006); Andoni et al. (2010); Andoni and Onak (2012). The current state of the art consists of a near-linear algorithm of Andoni et al. (2010) guaranteeing (log n)c-approximation (with a trade-off between the running time and the exponent c), and a constant factor approximation O(n2−2/7)-time algorithm of Chakraborty et al. (2018). To the best of our knowledge, neither algorithm has been implemented.

heading: 2.2 Edit Distance Embedding
text: As mentioned in the introduction, there has been a long line of research focused on designing embeddings of various variants of the edit distance into geometric space. For the edit distance as defined in the introduction, the best known algorithm is due to Ostrovsky and Rabani (2005), who designed an embedding into the Hamming space with distortion 2O( √ logn log logn). This algorithm was quite complex, and to the best of our knowledge has never been implemented. Recently, Chakraborty et al. (2016) gave a substantially different embedding with distortion O(k) where k is the edit distance between the original strings. The empirical evaluation of the algorithm, given in Zhang and Zhang (2017), demonstrated that the embedding yields good results in practice, and that the empirical distortion of this embedding is typically much lower than the worst case bound. Zhang and Zhang (2019) also proposed a novel string partition based algorithm for edit similarity join, without generating embeddings. Gomez-Bigorda et al. (2017) presented a novel approach for word embedding in Levenshtein space to improve downstream handwritten word spotting. Their method is similar to our Phase 1, but our model deals with longer sequences instead of words, and also adopts triplet loss training to capture sequence similarity (Phase 2) and CGK based algorithm to learn sequence alignment (Phase 3).

heading: 2.3 Similarity Capturing
text: Neural models are powerful to learn embeddings that capture latent similarity. For example, word2vec (Mikolov et al., 2013) learns semantic and syntactic similarity of a word from its
linguistic context. The idea has been extended to learn sentence or document similarity (Le and Mikolov, 2014), biological sequence similarity (Asgari and Mofrad, 2015; Ng, 2017). The aforementioned methods characterize input representations based on their context. A different approach aims to learn a distance metric, see Kulis (2013) for an overview. Among them, triplet network (Weinberger and Saul, 2009; Hoffer and Ailon, 2015; Schroff et al., 2015) uses triplet loss to learn similarity over triplets. Part of our model gets inspiration from triplet network.

heading: 3 Preliminaries
text: We use D to denote the alphabet, i.e., the set of symbols used in the strings. For any two strings x, y ∈ D∗ we use dE(x, y) to denote the edit distance between x and y, i.e., the minimum number of symbol insertions, deletions or substitutions needed to transform x into y. We define the distance metric d(x, y) = ||x − y||22. If the strings have different lengths, we pad the shorter string to make their lengths equal. In the binary case, d(x, y) corresponds to the Hamming distance between x and y.
The CGK algorithm is described below. Its input consists of a string x of length n (to be embedded), and a sequence of 6n random bits r, which are interpreted as a sequence of 3n random hash functions h1, · · · , h3n : {0, 1} → {0, 1}. It produces a sequence f(x, r), obtained by replicating each symbol in x at least once (the actual number is a random variable depending on x and r).
Algorithm 1 CGK Embedding Function f
Input: x ∈ {0, 1}n, and a random string r ∈ {0, 1}6n Output: f(x, r) ∈ {0, 1}3n
Interpret r as the description of h1, · · · , h3n : {0, 1} → {0, 1}. Initialization: i = 1, a = (0, · · · , 0) ∈ {0, 1}3n for j = 1, 2, · · · , 3n do aj = xi; i = i+ hj(xi); end for Set f(x, r) = a.

heading: 4 Learning-based Embedding Method
text: Recurrent Neural Network (RNN) models proved effective for sequence embedding tasks like language modeling (Mikolov et al., 2011), image captioning (Mao et al., 2015), protein sequence embedding (Bepler and Berger, 2019), etc. Long Short Term Memory (LSTM) (Hochreiter and Schmidhuber, 1997) and Gated Recurrent Unit (GRU) (Cho et al., 2014) utilize gates to overcome the long-term dependency problem and often yield improved empirical results. Our learning-based embedding model leverages two-layer GRU depicted in Figure 2. The input is a sequence of n characters in one-hot encoding, x = {x1, x2, ..., xn}. We feed the input sequence x into two-layer GRU and a linear layer to get the embedding sequence y = f(x). Here δi represents the dropout rate in GRU. We use Adam optimizer and 4:1 train:validation split for cross-validation to tune the hyper-parameters.
h1i = GRU 1(xi, h 1 i−1) (1) h2i = GRU 2(h1i δi, h 2 i−1) (2)
yi = Wh 2 i + b (3)
y = {y1, y2, ...yn} (4)

heading: 4.1 Phase 1: Absolute Loss as Warm Start
text: We use Phase 1 to tune the embedding such that the absolute difference between the edit distance and the embedding distance is small. In every iteration, we take a pair of input strings x and y, and pass it through two embedding networks denoted as f1, which share weights. The loss is defined as:
L1 = |dE(x, y)− d(f1(x), f1(y))| (5)

heading: 4.2 Phase 2: Triplet Loss for Similarity Capturing
text: Phase 2 initializes the network with weights computed in Phase 1. It leverages triplet loss (Weinberger and Saul, 2009) to capture the dependencies between string similarities. In each iteration we randomly choose an original string as the anchor and define positive and negative strings with respect to their edit distances from the anchor. More specifically, We randomly sample the positive pairs from top-5 edit distance and sample negative pairs as the top-30 distance in the embedded space, which is a fairly standard approach for triplet loss (Weinberger and Saul, 2009; Sablayrolles et al., 2019). The anchor, the positive and the negative string form a triplet. The triplets are passed through three networks, denoted by f2, which share common weights. For an anchor a, a positive string p and a negative string n, we formulate the triplet loss as:
L2 = max(0, d(f2(a), f2(p))− d(f2(a), f2(n)) + margin) (6)
Further, we set margin to be dE(a, n) − dE(a, p). Intuitively, we hope that the difference between the hamming distance between the positive and the negative pairs is larger than that of the edit distance, namely d(f2(a), f2(n))− d(f2(a), f2(p)) ≥ dE(a, n)− dE(a, p). See Figure 1 for illustration.

heading: 4.3 Phase 3: Insertion Loss for Hard Cases
text: Phase 3 is initialized using weights computed in Phase 2. During each iteration a pair of input strings is passed through two embedding networks denoted as f3, which share weights. Let x and y represent the original input strings and f3(x) and f3(y) denote their embeddings. Denote the CGK’ (a variant of CGK, see Algorithm 3 in the appendix) with random initialization as g, and we apply it on f3(x), f3(y) and get f ′ 3(x) = g(f3(x)), f ′3(y) = g(f3(x)). f ′ 3 is our final embedding function, which is essentially a concatenation of an embedding network f and the CGK’ algorithm g.
Optimization in Phase 3 has two different losses: the absolute loss and the insertion loss. The absolute loss (L3) ensures that the distance of the final embedding is close to the edit distance of x and y. The insertion loss is defined as follows. For each character c in f3(x), we
compare the two cases that with or without duplication of c to optimize the hash functions and the threshold. See Appendix A.1 for more details.
L3 = |dE(x, y)− d(f ′3(x), f ′3(y))| (7)
As we mentioned before, we use CGK’ instead of CGK because it restricts the number of replications of each symbol to be at most 2, therefore we can compare the two cases to get an approximation to the gradient, and then optimize the parameters in CGK’. In what follows we show that this modification does not affect the worst-case guarantees of the method (i.e., CGK’ with random initialization). See Appendix A.2 for the proof.
Theorem 1. The mapping f : {0, 1}n × {0, 1}4n → {0, 1}2n computed by Algorithm 2 satisfies the following properties:
(1) Given r ∈ {0, 1}4n and f(x, r) ∈ {0, 1}2n as the input, we can always decode x.
(2) For every x, y ∈ {0, 1}n, dE(x, y)/2 ≤ d(f(x, r), f(y, r)).
(3) There exists a constant c0 such that for every positive constant c ≥ c0 and every x, y ∈ {0, 1}n , d(f(x, r), f(y, r)) ≤ c · dE(x, y)2 with probability at least 1/2.

heading: 5 Experiments

heading: 5.1 Datasets
text: We evaluate our neural embedding with three datasets as in Zhang and Zhang (2017). Specifically, we use Gen50ks: a genetic sequence dataset from the human genome project; UniRef : UniRef90 protein sequence dataset from the UniProt project; and Trec: a reference dataset from Medline (an online medical information database). See Table 1 for their properties. Furthermore, following Zhang and Zhang (2017) we truncate some input strings to avoid dealing with very long outlier strings. For Gen50ks dataset, the string lengths sharply concentrate around 5000, so we set the truncation length to be 5000 and thresholding affects the distances only minimally. For UniRef and Trec dataset, string lengths vary drastically. In order to avoid biasing the original data distribution, we set a rather large threshold(1500 and 2500) so that only a small proportion(1.16% and 0.97%) of the strings exceed the threshold. For Gen50ks, UniRef and Trec dataset, we train our model with 1000, 2000, 2000 strings (including base and query) respectively, which means that we train with less than 2% data points in the whole dataset.

heading: 5.2 Nearest Neighbor Search

heading: 5.2.1 Exact Nearest Neighbor Search
text: We evaluate our model in the context of nearest neighbour search. We randomly select 100 queries and use the remainder of the dataset as the base set. Our goal is to find strings in the base set most similar to the query strings. To this end we use linear scan to identify the C sequences in the data set (called candidates) that are closest to the query in the embedded space. We compare embeddings generated by our neural model, CGK and its close variant CGK’, as well as the identity embedding (which is optimal if no insertions or deletions are needed). Since CGK and its variants are randomized, we measure the average of five independent runs. For all three datasets we observe that our neural model offers significant performance gains compared to the other embedding methods.

heading: 5.2.2 LSH-based Approximate Nearest Neighbor Search
text: In the previous section we used linear scan to find C nearest neighbors in the embedded space. Although this task can be often accomplished efficiently (e.g., using GPUs), in many scenarios more efficient approximate nearest neighbor search algorithms need to be employed. In this section we investigate one such instantiation employing Locality-Sensitive Hashing (LSH). We note that the same framework was used in Zhang and Zhang (2017) to evaluate CGK.
We use the cross-polytope LSH family under the Euclidean distance with multi-probe LSH (Andoni et al., 2015). For genetic dataset Gen50ks, we build 50 hash tables and 10-bit hash functions(We vary the number of hash bits and find 10-bit hash functions give the best performance). We test with five randomly selected 100 queries and record the mean and standard deviation as in Table 2.

heading: 5.3 String Similarity Join
text: Zhang and Zhang (2017) adopts the vanilla bit-sampling LSH for hamming distance, which does not suit our embedding as the neural embedded strings are continuous values instead of discrete characters. So for our string similarity join experiments, we continue to use the cross-polytope LSH family under the Euclidean distance with multi-probe LSH.
The LSH table parameters are the same with the approximate nearest neighbor setting. We run PassJoin (Li et al., 2011) to evaluate our join results.

heading: 5.4 Ablation Study
text: We further do ablation study to evaluate the function of three phases in our model. We notice a performance drop by removing Phase 1 or Phase 2. We explain this as Phase 1 provides good initialization which makes similarity learning easier while Phase 2 learns string similarity. Removing phase 3 generally does not lower the performance of top-1 recall much. This might be that these datasets do not contain many hard instances(like coexisting small shift and small substitution). Phase 3 does show its effectiveness in our synthetic hard case dataset, see Appendix A.3. We further show the standard deviation by testing with five different query sets, each of which contains 100 randomly selected strings.

heading: 6 Conclusion
text: In this paper, we introduce the idea of using neural embedding for computing nearest neighbor search under edit distance. Our method has three phases, i.e., the warm-start phase for generating an initial network with the correct scale, the triplet loss phase for learning relative distance among data points, and the back up phase for dealing with hard cases. Our last phase is non-trivial, because we designed a truncated version of CGK algorithm (aka CGK’) and proved that it has worst case performance guarantee. Our phase 3 directly optimizes CGK’ and easily solves hard cases. Overall, our method gives much better empirical results than the existing methods for nearest neighbor search.

heading: A Appendix
text: A.1 CGK’ algorithm and Phase 3
In Algorithm 2, we present the truncated version of CGK that we use in the paper. Compared with Algorithm 1, the main difference is in CGK’, every character will be duplicated for at most twice (with probability 0.5). Our Phase 3 is an optimized version of CGK’. We use Algorithm 3 in Phase 3. The main difference between Algorithm 2 and 3 is that we are using a threshold variable thres in the if-statement, to decide whether to duplicate the character or not. Moreover, the if-condition is evaluated based on the inner product between hash function hj and a one hot vector xi. Hence, Algorithm 3 is just a more general version of Algorithm 2.
Then how do we optimize the parameters in Algorithm 3(E.g., thres and h)? Since Algorithm 3 involves discrete decisions with if-statements, we manually define the gradients in Algorithm 4, by comparing the case whether the character is duplicated or not and calculate how it affects the loss.
Algorithm 2 CGK’ Embedding Function f
Input: x ∈ {0, 1}n, and a random string r ∈ {0, 1}4n Output: f(x, r) ∈ {0, 1}2n
Interpret r as the description of h1, · · · , h2n : {0, 1} → {0, 1}. Initialization: j = 1, a = (0, · · · , 0) ∈ {0, 1}2n for i = 1, 2, · · · , n do if hj(xi) then aj = xi; j = j + 1;
else aj+1 = aj = xi; j = j + 2;
end if end for Set f(x, r) = a.
Algorithm 3 Learning-Augmented Embedding Function f ′
Input: x where xi is a one-hot vector, H is a 2 × 2n matrix interpreted as h1, ..., h2n, thres ∈ R after optimization Output: f ′(x), set Duplicate which records the duplicated bits in f ′(x) Initialization: j = 1, a = 02×2n, Duplicate = ∅ for i = 1, 2, · · · , n do if hj · xi < thres then aj = xi; j = j + 1;
else aj+1 = aj = xi; Duplicate← Duplicate ⋃ {j}
j = j + 2; end if end for Set f ′(x) = a.
A.2 Proof of the Main Theorem
For simplicity, denote the two embedded strings f(x, r), f(y, r) as fx, fy. Below we always use i to denote the index for the input strings, and use j to denote the index for the embedded strings. We use idx(x, j) to denote the corresponding index i for producing the
Algorithm 4 Optimization Scheme for h and thres in Algorithm 3
Input: x, y, f ′(x), f ′(y), H interpreted as h1, ..., h2n, thres, set Duplicate in Algorithm 3, learning parameters , η Output: H and thres after optimization Initialization j = 1 L = |dH(f ′(x), f ′(y))− dE(x, y)|; for i = 1, 2, · · · , n do g(x) = f ′(x) if j ∈ Duplicate then
Remove g(x)j+1 from g(x); L′ = |dH(g(x), f ′(y))− dE(x, y)|; if L′ < L then thres = thres+ ; hj = hj − η · xi; end if j = j + 2; else Duplicate g(x)j in g(x); L′ = |dH(g(x), f ′(y))− dE(x, y)|; if L′ < L then thres = thres− ; hj = hj + η · xi;
end if j = j + 1;
end if end for
j-th index of output f(x, r). Define ∆j , idx(x, j)− idx(y, j) as the input index difference between x and y at embedding index j.
In Algorithm 2, given the input x and index i, we may append one or two copies of xi into the output. We call the first copy the major copy, and the second copy the minor copy. The major copy always exists in the output, but the minor copy exists with probability 1/2, depending on the hash function hj . For any index j, if f x j and f y j are both major copies or both minor copies, we say j is aligned. Otherwise, j is not aligned. Initially, fx1 and f y 1 are major copies, therefore index 1 is aligned. See figure 7 for illustration.
We scan fx and fy from left to right, and for every index j such that j+1 is not aligned but j is aligned, we find the next aligned index j′, and group all the indices j+1, j+2, · · · , j′−1 as a sub-index string for the aligned index j. For the corner case that j′ does not exist, we pick j′ as the minimum final j value for computing fx and fy (So starting from j′, fx or fy will be padded with zeros).
Now we focus on the aligned indices. For an aligned index j without a sub-index string, we know index j+ 1 is also aligned, otherwise j+ 1 will be inside the sub-index string for index j. In this case, we can show ∆j+1−∆j = 0 by discussing whether index j + 1 has major or minor copies.
On the other hand, consider an aligned index j with a sub-index string. In this case, we know both fxj and f y j are major copies. Without loss of generality, we may assume f x j+1 is a major copy and fyj+1 is a minor copy (the other case is symmetric). We have the following lemma for a few facts related to the sub-index string.
Lemma 2. Denote the next aligned index by j′ > j + 1. Assume the sub-index string has length t , j′ − j − 1 > 0. Given T such that T/2 ∈ Z+, we have
(1) fxj′ and f y j′ are major copies,
(2) t ≤ T holds with probability 1− 2−T ,
(3) Conditioned on t ≤ T ,
∆j′ −∆j = {
1, w.p. 2/3 0, w.p. 1/3 ,
Proof. Since j′ is the first aligned index after j, we know that for any j < jo < j ′, jo is not aligned, therefore one of fxjo and f y jo
is major and the other one is minor. By Algorithm 2, for the string with the minor copy, with probability 1, the next copy on jo + 1 is a major copy; and for the string with the major copy, the next copy on jo + 1 is a major copy or minor copy with equal probability. However, if both copies on jo + 1 is major, we know jo + 1 is aligned, and thus j
′ = jo + 1. In other words, this case only happens for the index jo = j
′ − 1, and for other indices, the two strings are not aligned, and have major copies in turn. That already proves (1).
Since the two strings have major copies in turn, and only major copies will increment the value of idx(x, j), we know
∆j′ −∆j = {
1, if t is odd 0, otherwise ,
See Figure 7 for the two possible cases. Moreover, every step from j + 1 to j′ holds with probability 1/2, so the probability that the sub-index string has length t is 2−t. By summing over the probabilities of t from 1 to T , we proved (2). Finally, (3) holds by comparing the probabilities of t ≤ T being odd and being even, which is exactly 2 : 1.
Remark 1. Based on Lemma 2(2), if there are l sub-index strings, and for a given T (to be determined later), the probability that all sub-index strings are within length T is bounded by 1− l · 2−T using union bound. Below we discuss the case conditioned on this event.
Lemma 2(3) states that if an aligned index j has a sub-index string, and fxj+1 is a major copy, then ∆j will be incremented by 1 with probability 2/3, and stay unchanged with probability 1/3. Since fxj , f y j are major copies, we know that this case happens with probability 1/4. The symmetric case where fxj+1 is a minor copy and f y j+1 is a major copy also happens with probability 1/4.
Combine the two possible cases for aligned index j (with or without sub-index string), and assuming the next aligned major index is j′. If fxj and f y j are minor copies, or are the same, we have ∆j′ −∆j = 0 by simple case analysis. Otherwise, we have:
∆j′ −∆j = { 1, w.p. 1/6 0, w.p. 2/3 −1, w.p. 1/6 , (8)
This is because for the two aligned major copies at index j, with probability 1/2, the next index j + 1 is still aligned, and as a result ∆j does not change. With probability 1/2, there exists a sub-index string for index j, but conditioned on this, the probability that ∆j does not change is 1/3. So the total probability for being unchanged is 1/2+1/6 = 2/3. The other two cases are symmetric, so each has probability (1− 2/3)/2 = 1/6. This defines a random walk process for ∆j , and the remaining analysis is similar to the analysis in Chakraborty et al. (2016).
Assume that dE(x, y) = k. Let x = x (0), x(1), · · · , x(k) = y be a series of strings such that dE(x (l−1), x(l)) = 1. Let il be the first index on which x
(l−1) and x(l) differ. For simplicity we assume that i1 < · · · < ik (and we will later show this is without loss of generality). Let dj be the difference between deleted and inserted bits between x and y before the index j. Therefore, d0 = 0, and
dj =  dj−1, idx(x, j) 6∈ {i1, · · · , ik} dj−1 − 1, idx(x, j) = il, idx(x, j − 1) 6= il, x(l) is obtained by deletion dj−1 + 1, idx(x, j) = il, idx(x, j − 1) 6= il, x(l) is obtained by insertion dj−1 otherwise , (9)
dj denotes the required length of “shift” between f x and fy. In other words, for j such that idx(x, j) ∈ (il, il+1), and idx(x, j)− idx(y, j) = ∆j = dj , we know fxj = f y j . Moreover, for any j′ ≥ j such that idx(x, j′) ∈ [idx(x, j), il+1), we know that fxj′ = f y j′ holds as well, because the same hash function will be applied to both strings after idx(x, j).
By modeling ∆j and dj as a chasing game between a cat and a dog with a kennel, the following lemma was proved in Chakraborty et al. (2016).
Lemma 3 (Lemma 4.4 in Chakraborty et al. (2016)). If dE(x, y) = k, then
Pr(|{j : fxj 6= f y j , j is an aligned major index}| ≤ l) ≥ l∑ t=0 q(t, k)
Where q(t, l) denotes the probability that the random walk process defined by (8) starting at the origin, reaches the point l at time t for the first time.
As discussed in Chakraborty et al. (2016), the assumption that i1, · · · , ik are strictly monotone is without loss of generality, because it suffices to modify the updating rule of dj in (9) such that dj and dj−1 can be differed by more than 1 unit. Once dj is properly defined, Lemma 3 still applies.
The sum ∑l
t=0 q(t, k) in Lemma 3 is easy to bound:
Lemma 4. For any k, l ∈ N, with probability more than 1− e− l24 , it holds that l∑
t=0
q(t, k) ≥ 1− 12k √ 6
l
In particular, ∑7776k2
t=0 q(t, k) ≥ 2 3 .
Proof. Below is a well known fact about random walks that can be found e.g. (Theorem 2.17 in Levin and Peres (2017)). For any k, l ∈ N , it holds that:
l∑ t=0 r(t, k) ≥ 1− 12k√ l
where r(t, k) denotes the probability a simple random walk starting at the origin reaches point k for the first time in t steps. Let m be the number of non-lazy steps during a t-step random walk defined in (8). By applying Chernoff Bounds, for any 0 < δ < 1 we have:
P (m > (1− δ)1 3 t) > 1− e− δ 2 6 t
Therefore, with probability more than 1−e− δ 2
6 t, we are performing more than (1−δ) 13 t-steps simple random walk. Setting δ = 12 gives us the result in Lemma 4.
Now we are ready to prove our Theorem 1.
Proof of Theorem 1. (1) is trivially true, because we can simulate Algorithm 2 using the random string r to decide for each index of fx whether it is a major copy or not.
To see (2) is true, we need to do case analysis. We scan fx and fy from left to right, and skip all indices that are the same. For the first different index j, there are three cases:
1. j is aligned major, and j + 1 is aligned minor.
2. j is aligned major, and j + 1 is also aligned major.
3. j is aligned major, and j + 1 is not aligned.
For the first two cases, it suffices to replace the bit at idx(x, j) of x, and we can keep scanning starting from the next aligned major. For the third case, we can do induction on the length t of the sub-index string for j, to show that it suffices to make at most s edits if there are s different bits from j to j + t. Without loss of generality, we assume that the index j + 1 of fx is a major copy while j + 1 of fy is a minor copy.
• If t = 1, which means j + 2 is aligned major. In this case, if bits at index j + 1 of fx and fy are matched, it suffices to edit the bit at index j. Otherwise, it suffices to delete idx(x, j) of x, and replace the bit at idx(x, j + 1) of x to match y.
• If t = 2, which means j + 3 is aligned major, and the index j of fy is a major copy. In this case, we check whether the bits at j + 2 for fx, fy are the same.
– If yes, it means, idx(y, j + 2) of y and idx(x, j + 2) of x are the same. In this case, it suffices to replace idx(x, j) of x to match y.
– If no, it suffices to replace both idx(x, j), idx(x, j + 1) of x to match y.
• If t > 2, we also check whether the bits at j + t for fx, fy are the same.
– If yes, it means, idx(y, j + t) of y and idx(x, j + t) of x are the same. Then we may reduce the analysis to the t− 2 case. By induction, we know that from j to j + t− 2, we can make the proper edit to match x and y.
– If no, it means idx(y, j + t) of y and idx(x, j + t) of x are different. We make one edit on idx(x, j+ t) to match idx(y, j+ t) of y, and then reduce the analysis to the t− 2 case.
Notice that in the above two sub-cases, we did not analyze the case at index j+t−1. This is because this index is not aligned, and the minor copy is included in the analysis of index j to j + t− 2, while the major copy is included in the analysis of index j + t.
The above analysis shows that it suffices to make at most d(fx, fy) edits to match x and y until one of fx or fy starts to pad zeros. Since there are at most d(fx, fy) deletions or insertions on x, and originally x and y have the same length, we know that there are at most d(fx, fy) padded zeros. Combine the two cases together, we have dE(f x, fy)/2 ≤ d(fx, fy).
(3) Apply Lemma 3, we know that with probability (1 − e− l24 ) · (1 − 12k √
6 l ), there are
at most l aligned major indices that satisfies fxj 6= f y j . Notice that, if for any indices, if fxj = f y j , it does not affect d(f x, fy). Hence below we consider other cases when fxj 6= f y j :
• If j is an aligned minor, we know that j−1 is aligned major such that fxj 6= f y j , and
also j + 1 is an aligned major index. Thus the number of such indices is at most l.
• If j is not aligned, we know that j belongs to a sub-index string for an aligned major index j′ < j. Notice that fxj 6= f y j , otherwise j
′ won’t have sub-index string. We bound the number of such indices below.
To recap, we need to bound the expected sum of lengths of sub-index strings that start from an aligned major index j such that fxj 6= f y j . Since the number of such strings is l, and the expected length of each string is at most 2, it follows that the expected sum of lengths is at most 2l. We can thus use Markov inequality to show that this quantity is at most 20l with probability at least 9/10.
We note that in Lemma 3, we did not consider the comparison between fx and fy when one of them has padded zeros. However, it is easy to see that in this case every edit operation can only incur one unit of cost in d(fx, fy), which is not the worst case.
Therefore, with probability at least (1− e− l24 ) · (1− 12k √
6 l )− 0.1, the hamming distance
is at most 20l. Let l = ck 2
20 , we know the probability is at least (1− e− l24 ) · (1− 12k √ 6
l )− 0.1
=(1− e− ck 2 480 ) · (1− 12 √
120√ c )− 0.1
≥(1− e− c480 ) · (1− 12 √
120√ c )− 0.1
The last inequality holds because k ≥ 1, otherwise the hamming distance is 0. Therefore it suffices pick c0 = 50000, and the expression above is larger than 0.5. Notice that we did not carefully tune the constants here.
A.3 Synthetic Data Set
Although Phase 1+2 has good performance for most data sets, we can easily construct synthetic data sets for which it will fail. For example, given a string x, applying 1-bit shift to the right gives rise to a large hamming distance but the edit distance is only two. If this 1-bit shift coexists with a 3-bit substitution (so that the hamming distance and edit distance are both equal to three), it would be quite “hard” for Phase 1+2 to find nearest neighbors under edit distance. However, adding Phase 3 easily solves the problem, and gives improved accuracy on the challenging hard cases.
We have generated a synthetic data set to illustrate the algorithm effectiveness. First we have chosen some prefix strings from the Gen50ks dataset as the query set. Then, for each query, we generate its small shifts (one or two) and small substitution strings (three or four), which are used as the base set. For each query we want to find the closest edit distance string in the base set. The performance of all studied algorithms on this data set are shown in Table 6. It can be seen that adding Phase 3 improves the performance of our method.
A.4 Visualization
We visualize the embedding results for both CGK and our model using t-SNE (van der Maaten and Hinton, 2008). For CGK embedding, the points distribute over the 2D space randomly no matter what hyper-parameters are used. For neural embedding, on the other hand, points are well clustered. Figure 8 shows 2D t-SNE projections with perplexity 8 and learning rate 10.

Review summaries:
In this paper, the authors propose an approach for learning embeddings for strings using a three-phase approach. Each phase uses a different neural network to learn embeddings for strings such that the distance between strings in embedding space approximates the edit distance between the strings. A modest set of empirical results suggests that the proposed approach outperforms hand-crafted embeddings.