skip to main content
10.1145/1060590.1060623acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Low distortion embeddings for edit distance

Published: 22 May 2005 Publication History

Abstract

We show that 0,1d endowed with edit distance embeds into l1 with distortion 2O(√log dlog log d). We further show efficient implementations of the embedding that yield solutions to various computational problems involving edit distance. These include sketching, communication complexity, nearest neighbor search. For all these problems, we improve upon previous bounds.

References

[1]
A. Andoni, M. Deza, A. Gupta, P. Indyk, and S. Raskhodnikova. Lower bounds for embedding edit distance into normed spaces. In Proc. SODA 2003, pages 523--526.
[2]
Z. Bar-Yossef, T.S. Jayram, R. Krauthgamer, and R. Kumar. Approximating edit distance efficiently. In Proc. FOCS 2004.
[3]
T. Batu, F. Ergun, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, and R. Sami. A sublinear algorithm for weakly approximating edit distance. In Proc. STOC 2003.
[4]
A. Broder, S. Glassman, M. Manasse, and G. Zweig. Syntactic clustering of the Web. In Proc. of the 6th Int'l World Wide Web Conf., 1997, pages 391--404.
[5]
G. Cormode and S. Muthukrishnan. The string edit distance matching problem with moves. In Proc. SODA 2002, pages 667--676.
[6]
G. Cormode, M. Paterson, C.S. Sahinalp, and U. Vishkin. Communication complexity of document exchange. In Proc. SODA 2000.
[7]
P. Indyk. Approximate nearest neighbor under edit distance via product metrics. In Proc. SODA 2004, pages 646--650.
[8]
P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proc. STOC 1998, pages 604--613.
[9]
E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM Journal on Computing, 30(2):457--474, 2000. (Preliminary version appeared in Proc. STOC 1998.)
[10]
V.I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Doklady Akademii Nauk SSSR, 163(4):845--848, 1965 (Russian). English translation in Soviet Physics Doklady, 10(8):707--710, 1966.
[11]
W.J. Masek and M.S. Paterson. A faster algorithm for computing string edit distnace. Journal of Computer and Systems Sciences, 20(1):18-31, 1980.
[12]
S. Muthukrishnan and S.C. Sahinalp. Approximate nearest neighbors and sequence comparison with block operations. In Proc. STOC 2000, pages 416--424.

Cited By

View all
  • (2021)MP-RW-LSHProceedings of the VLDB Endowment10.14778/3484224.348422614:13(3267-3280)Online publication date: 28-Oct-2021
  • (2018)Approximating edit distance in truly subquadratic timeProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175346(1170-1189)Online publication date: 7-Jan-2018
  • (2016)On the Security of Key Extraction From Measuring Physical QuantitiesIEEE Transactions on Information Forensics and Security10.1109/TIFS.2016.254368711:8(1796-1806)Online publication date: Aug-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
May 2005
778 pages
ISBN:1581139608
DOI:10.1145/1060590
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. edit distance
  2. low distortion embeddings
  3. metric spaces

Qualifiers

  • Article

Conference

STOC05
Sponsor:
STOC05: Symposium on Theory of Computing
May 22 - 24, 2005
MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)MP-RW-LSHProceedings of the VLDB Endowment10.14778/3484224.348422614:13(3267-3280)Online publication date: 28-Oct-2021
  • (2018)Approximating edit distance in truly subquadratic timeProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175346(1170-1189)Online publication date: 7-Jan-2018
  • (2016)On the Security of Key Extraction From Measuring Physical QuantitiesIEEE Transactions on Information Forensics and Security10.1109/TIFS.2016.254368711:8(1796-1806)Online publication date: Aug-2016
  • (2012)Embedding edit distance to enable private keyword searchHuman-centric Computing and Information Sciences10.1186/2192-1962-2-22:1Online publication date: 23-Feb-2012
  • (2011)Embedding Edit Distance to Allow Private Keyword Search in Cloud ComputingSecure and Trust Computing, Data Management and Applications10.1007/978-3-642-22339-6_13(105-113)Online publication date: 2011
  • (2010)Approximating Tree Edit Distance through String Edit DistanceAlgorithmica10.5555/3118232.311851857:2(325-348)Online publication date: 1-Jun-2010
  • (2010)Lower bounds for edit distance and product metrics via Poincaré-type inequalitiesProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873618(184-192)Online publication date: 17-Jan-2010
  • (2009)LCS Approximation via Embedding into Local Non-repetitive StringsProceedings of the 20th Annual Symposium on Combinatorial Pattern Matching - Volume 557710.5555/3127091.3127100(92-105)Online publication date: 22-Jun-2009
  • (2009)LCS Approximation via Embedding into Local Non-repetitive StringsCombinatorial Pattern Matching10.1007/978-3-642-02441-2_9(92-105)Online publication date: 2009
  • (2008)Earth mover distance over high-dimensional spacesProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347120(343-352)Online publication date: 20-Jan-2008
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media