Fetching the paper…
Reading the bibliography…
We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor; specifically, for strings of length n and every fixed epsilon>0, it can compute a (log n)^O(1/epsilon) approximation in n^(1+epsilon) time.
Probability inequalities for sums of bounded random variables
Wassily Hoeffding · 1963
Earlier work this paper cites.
Binary codes capable of correcting deletions, insertions, and reversals (in russian)
Vladimir I. Levenshtein · 1966
Earlier work this paper cites.
The string-to-string correction problem
Robert A. Wagner and Michael J. Fischer · 1974
Earlier work this paper cites.
Longest common subsequences of two random sequences
V. Chvatal and D. Sankoff · 1975
Earlier work this paper cites.
A faster algorithm computing string edit distances
William J. Masek and Mike Paterson · 1980
Earlier work this paper cites.
Algorithms on strings, trees, and sequences
Dan Gusfield · 1997
Earlier work this paper cites.
Incremental string comparison
Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt · 1998
Earlier work this paper cites.
Bounding the expected length of longest common subsequences and forests
R. A. Baeza-Yates, R. Gavaldà, G. Navarro, and R. Scheihing · 1999
Earlier work this paper cites.
Communication complexity of document exchange
Graham Cormode, Mike Paterson, Suleyman Cenk Sahinalp, and Uzi Vishkin · 2000
Earlier work this paper cites.
Spot-checkers
Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Manesh Viswanathan · 2000
Earlier work this paper cites.
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani · 2000
Earlier work this paper cites.
Approximate nearest neighbors and sequence comparison with block operations
S. Muthukrishnan and Cenk Sahinalp · 2000
Earlier work this paper cites.
Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein · 2001
Cited alongside, same era.
Algorithmic aspects of geometric embeddings (tutorial)
Piotr Indyk · 2001
Cited alongside, same era.
A guided tour to approximate string matching
Gonzalo Navarro · 2001
Cited alongside, same era.
Space lower bounds for distance approximation in the data stream model
Michael Saks and Xiaodong Sun · 2002
Cited alongside, same era.
A sublinear algorithm for weakly approximating edit distance
Tuğkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami · 2003
Cited alongside, same era.
Sequence Distance Embeddings
Graham Cormode · 2003
Cited alongside, same era.
Estimating the distance to a monotone function
Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu · 2007
Later among the works it cites.
The string edit distance matching problem with moves
Graham Cormode and S. Muthukrishnan · 2007
Later among the works it cites.
Collection of open problems on low-distortion embeddings of finite metric spaces
Jiří Matoušek · 2007
Later among the works it cites.
Low distortion embedding for edit distance
Rafail Ostrovsky and Yuval Rabani · 2007
Later among the works it cites.
Fast and compact regular expression matching
Philip Bille and Martin Farach-Colton · 2008
Later among the works it cites.
Edit distance under block operations
Süleyman Cenk Sahinalp · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Low distortion embeddings of finite metric spaces
Piotr Indyk and Jiří Matoušek · 2003
Cited alongside, same era.
Approximating edit distance efficiently
Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar · 2004
Cited alongside, same era.
Optimal approximations of the frequency moments of data streams
Piotr Indyk and David Woodruff · 2005
Cited alongside, same era.
Oblivious string embeddings and edit distance approximations
Tuğkan Batu, Funda Ergün, and Cenk Sahinalp · 2006
Cited alongside, same era.
Nonembeddability theorems via Fourier analysis
Subhash Khot and Assaf Naor · 2006
Cited alongside, same era.
Improved lower bounds for embeddings into
Robert Krauthgamer and Yuval Rabani · 2006
Cited alongside, same era.
Approximating edit distance in near-linear time
Alexandr Andoni and Krzysztof Onak · 2009
Later among the works it cites.
Improved bounds on the average length of longest common subsequences
G. S. Lueker · 2009
Later among the works it cites.
Lower bounds for edit distance and product metrics via Poincaré-type inequalities
Alexandr Andoni, T.S. Jayram, and Mihai Pǎtraşcu · 2010
Closest in time.
The computational hardness of estimating edit distance
Alexandr Andoni and Robert Krauthgamer · 2010
Closest in time.
Near-tight bounds for testing Ulam distance
Alexandr Andoni and Huy L. Nguyen · 2010
Closest in time.