Name
Abstract | ||
|---|---|---|
We show that {0, 1}d endowed with edit distance embeds into ℓ1 with distortion 2O(&sqrt;log d log log d). We further show efficient implementation 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1284320.1284322 | J. ACM |
Keywords | Field | DocType |
nearest neighbor search,previous bound,yield solution,distance embeds,dimension reduction,metric embeddings,computations on discrete structures,efficient implementation,various computational problem,sketching,low distortion embeddings,levenshtein distance,log log,communication complexity,pattern matching,edit distance | Edit distance,Discrete mathematics,Combinatorics,Embedding,Dimensionality reduction,Computer science,Levenshtein distance,Communication complexity,Pattern matching,Distortion,Nearest neighbor search | Journal |
Volume | Issue | ISSN |
54 | 5 | 0004-5411 |
ISBN | Citations | PageRank |
1-58113-960-8 | 43 | 2.20 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rafail Ostrovsky | 1 | 8743 | 588.15 |
| Yuval Rabani | 2 | 2265 | 274.98 |