Approximating edit distance in near-linear time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating edit distance in near-linear time

Full text

Pdf (563 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 41st annual ACM symposium on Theory of computing table of contents

Bethesda, MD, USA

SESSION: Approx algorithms I table of contents

Pages 199-204

Year of Publication: 2009

ISBN:978-1-60558-506-2

Authors

Alexandr Andoni	MIT, Cambridge, MA, USA
Krzysztof Onak	MIT, Cambridge, MA, USA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 95, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1536414.1536444 What is a DOI?

ABSTRACT

We show how to compute the edit distance between two strings of length n up to a factor of 2^{(O-tilde(sqrt(log n)))} in n^(1+o(1)) time. This is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n^(1/3+o(1)) approximation. Previously, approximation of 2^{Õ √log n)} was known only for embedding edit distance into l₁, and it is not known if that embedding can be computed in less than a quadratic time.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alexandr Andoni , Piotr Indyk , Robert Krauthgamer, Earth mover distance over high-dimensional spaces, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.343-352, January 20-22, 2008, San Francisco, California
	2	Ziv Bar-Yossef , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Approximating Edit Distance Efficiently, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.550-559, October 17-19, 2004 [doi>10.1109/FOCS.2004.14]
	3	Tugkan Batu , Funda Ergün , Joe Kilian , Avner Magen , Sofya Raskhodnikova , Ronitt Rubinfeld , Rahul Sami, A sublinear algorithm for weakly approximating edit distance, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780590]
	4	Tuğkan Batu , Funda Ergun , Cenk Sahinalp, Oblivious string embeddings and edit distance approximations, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.792-801, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109644]
	5	J. Bourgain. On Lipschitz embedding of finite metric spaces into Hilbert space. Israel Journal of Mathematics, 52:46--52, 1985.
	6	Bo Brinkman , Moses Charikar, On the Impossibility of Dimension Reduction in \ell _1, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.514, October 11-14, 2003
	7	Moses Charikar , Amit Sahai, Dimension Reduction in the \ell _1 Norm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.551-560, November 16-19, 2002
	8	Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
	9	G. Cormode. Sequence Distance Embeddings. Ph.D. Thesis. University of Warwick, 2003.
	10	Graham Cormode , Mike Paterson , Süleyman Cenk Sahinalp , Uzi Vishkin, Communication complexity of document exchange, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.197-206, January 09-11, 2000, San Francisco, California, United States
	11	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	12	P. Indyk. Algorithmic aspects of geometric embeddings (tutorial). Proc. of FOCS, pages 10--33, 2001.
	13	Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006 [doi>10.1145/1147954.1147955]
	14	S. Khot and A. Naor. Nonembeddability theorems via fourier analysis. Math. Ann., 334(4):821--852, 2006. Preliminary version appeared in FOCS'05.
	15	Robert Krauthgamer , Yuval Rabani, Improved lower bounds for embeddings into L₁, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1010-1017, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109669]
	16	J. Lee and A. Naor. Embedding the diamond graph in L_p and dimension reduction in L₁. Geometric and Functional Analysis (GAFA), 14(4):745--747, 2004.
	17	V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals (in russian). Doklady Akademii Nauk SSSR, 4(163):845--848, 1965. Appeared in English as: V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10(8), 707--710, 1966.
	18	W. J. Masek and M. Paterson. A faster algorithm computing string edit distances. J. Comput. Syst. Sci., 20(1):18--31, 1980.
	19	Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
	20	E. W. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1(2):251--266, 1986.
	21	Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
	22	Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Journal of the ACM (JACM), v.54 n.5, p.23-es, October 2007 [doi>10.1145/1284320.1284322]