Lower bounds for embedding edit distance into normed spaces

A. Andoni; M. Deza; A. Gupta; P. Indyk; S. Raskhodnikova

Lower bounds for embedding edit distance into normed spaces

A. Andoni, M. Deza, A. Gupta, P. Indyk, S. Raskhodnikova

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

Several computational experiments were performed to improve the lower bound of 3/2. As a result, it was possible to estimate the distortion for embedding of the edit metric over binary strings of length up to d into l₁ or square of l₂, for small values of d.

Original language	English (US)
Pages	523-526
Number of pages	4
State	Published - 2003
Event	Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: Nov 2 1998 → Nov 3 1998

Other

Other	Configuralble Computing: Technology and Applications
Country/Territory	United States
City	Boston, MA
Period	11/2/98 → 11/3/98

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{3036f33cf2064334bbf19da831dfe6f9,

title = "Lower bounds for embedding edit distance into normed spaces",

abstract = "Several computational experiments were performed to improve the lower bound of 3/2. As a result, it was possible to estimate the distortion for embedding of the edit metric over binary strings of length up to d into l1 or square of l2, for small values of d.",

author = "A. Andoni and M. Deza and A. Gupta and P. Indyk and S. Raskhodnikova",

year = "2003",

language = "English (US)",

pages = "523--526",

note = "Configuralble Computing: Technology and Applications ; Conference date: 02-11-1998 Through 03-11-1998",

}

TY - CONF

T1 - Lower bounds for embedding edit distance into normed spaces

AU - Andoni, A.

AU - Deza, M.

AU - Gupta, A.

AU - Indyk, P.

AU - Raskhodnikova, S.

PY - 2003

Y1 - 2003

N2 - Several computational experiments were performed to improve the lower bound of 3/2. As a result, it was possible to estimate the distortion for embedding of the edit metric over binary strings of length up to d into l1 or square of l2, for small values of d.

AB - Several computational experiments were performed to improve the lower bound of 3/2. As a result, it was possible to estimate the distortion for embedding of the edit metric over binary strings of length up to d into l1 or square of l2, for small values of d.

UR - http://www.scopus.com/inward/record.url?scp=0038754128&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038754128&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0038754128

SP - 523

EP - 526

T2 - Configuralble Computing: Technology and Applications

Y2 - 2 November 1998 through 3 November 1998

ER -

Lower bounds for embedding edit distance into normed spaces

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this