Fetching the paper…
Reading the bibliography…
The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other.
C. Schensted, Longest increasing and decreasing subsequences , Canadian Journal of Mathematics 13
1961
Earlier work this paper cites.
VI Levenshtein, Binary Codes Capable of Correcting Deletions, Insertions and Reversals , Soviet Physics Doklady 10
1966
Earlier work this paper cites.
Peter Weiner, Linear pattern matching algorithms , Proceedings of the 14th Annual Symposium on Switching and Automata Theory (Swat 1973) (Washington, DC, USA), SWAT ’73, IEEE Computer Society, 1973, pp. 1–11
1973
Earlier work this paper cites.
Robert A. Wagner and Michael J. Fischer, The string-to-string correction problem , J. ACM 21
1974
Earlier work this paper cites.
Michael L. Fredman, On computing the length of longest increasing subsequences , Discrete Mathematics 11
1975
Earlier work this paper cites.
Edward M. McCreight, A space-economical suffix tree construction algorithm , J. ACM 23
1976
Earlier work this paper cites.
William J. Masek and Michael S. Paterson, A faster algorithm computing string edit distances , Journal of Computer and System Sciences 20
1980
Earlier work this paper cites.
Esko Ukkonen, Algorithms for approximate string matching , Inf. Control 64
1985
Earlier work this paper cites.
Maxime Crochemore and Wojciech Rytter, Text algorithms , Oxford University Press, 1994
1994
Earlier work this paper cites.
Esko Ukkonen, On-line construction of suffix trees , Algorithmica 14
1995
Earlier work this paper cites.
Dan Gusfield, Algorithms on strings, trees, and sequences - computer science and computational biology , Cambridge University Press, 1997
1997
Cited alongside, same era.
Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt, Incremental string comparison , SIAM J. Comput. 27
1998
Cited alongside, same era.
Gonzalo Navarro, A guided tour to approximate string matching , ACM Comput. Surv. 33
2001
Cited alongside, same era.
Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami, A sublinear algorithm for weakly approximating edit distance , Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’03, ACM, 2003, pp. 316–324
2003
Cited alongside, same era.
Z. Bar-Yossef, T.S. Jayram, R. Krauthgamer, and R. Kumar, Approximating edit distance efficiently , Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, Oct 2004, pp. 550–559
Funda Ergün and Hossein Jowhari, On distance to monotonicity and longest increasing subsequence of a data stream , Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, 2008, pp. 730–736
2008
Later among the works it cites.
2008
Later among the works it cites.
Alexandr Andoni and Krzysztof Onak, Approximating edit distance in near-linear time , Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’09, ACM, 2009, pp. 199–204
2009
Later among the works it cites.
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak, Polylogarithmic approximation for edit distance and the asymmetric query complexity , 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, 2010, pp. 377–386
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2004
Cited alongside, same era.
David Liben-Nowell, Erik Vee, and An Zhu, Finding longest increasing and common subsequences in streaming data , Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, 2005, pp. 263–272
2005
Cited alongside, same era.
Tuğkan Batu, Funda Ergun, and Cenk Sahinalp, Oblivious string embeddings and edit distance approximations , Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (Philadelphia, PA, USA), SODA ’06, Society for Industrial and Applied Mathematics, 2006, pp. 792–801
2006
Cited alongside, same era.
Anna Gál and Parikshit Gopalan, Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence , 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, 2007, pp. 294–304
2007
Cited alongside, same era.
Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar, Estimating the sortedness of a data stream , Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, 2007, pp. 318–327
2007
Cited alongside, same era.
Xiaoming Sun and David P. Woodruff, The communication and streaming complexity of computing the longest common and increasing subsequences , Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, 2007, pp. 336–345
2007
Cited alongside, same era.
2010
Later among the works it cites.
Ho-Leung Chan, Tak Wah Lam, Lap-Kei Lee, Jiangwei Pan, Hing-Fung Ting, and Qin Zhang, Edit distance to monotonicity in sliding windows , Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, 2011, pp. 564–573
2011
Later among the works it cites.
Michael E. Saks and C. Seshadhri, Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance , Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, 2013, pp. 1698–1709
2013
Later among the works it cites.
Arturs Backurs and Piotr Indyk, Edit distance cannot be computed in strongly subquadratic time (unless SETH is false) , Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (New York, NY, USA), STOC ’15, ACM, 2015, pp. 51–58
2015
Later among the works it cites.
Karl Bringmann and Marvin Künnemann, Quadratic conditional lower bounds for string problems and dynamic time warping , IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, 2015, pp. 79–97
2015
Later among the works it cites.
Djamal Belazzougui and Qin Zhang, Edit distance: Sketching, streaming and document exchange , In Proc. of IEEE Symposium on Foundations of Computer Science (FOCS 2016), 2016, p. to appear
2016
Closest in time.
Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký, Streaming algorithms for embedding and computing edit distance in the low distance regime , Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, 2016, pp. 712–725
2016
Closest in time.