Low distortion embeddings for edit distance

被引：55

作者：

Ostrovsky, Rafail ^{[1
]}

Rabani, Yuval

机构：

[1] Univ Calif Los Angeles, Dept Comp Sci, Los Angeles, CA 90095 USA

[2] Univ Calif Los Angeles, Dept Math, Los Angeles, CA 90095 USA

[3] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

JOURNAL OF THE ACM | 2007年 / 54卷 / 05期

关键词：

algorithms; theory; pattern matching; computations on discrete structures; edit distance; Levenshtein distance; metric embeddings; dimension reduction; sketching; communication; complexity; nearest neighbor search;

D O I：

10.1145/1284320.1284322

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show that (0, 1)(d) endowed with edit distance embeds into B, with distortion 2(0)(root log d 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.

引用

页数：16

共 13 条

[1] Andoni A, 2003, SIAM PROC S, P523
[2] BARYOSSEF Z, 2004, P S FDN COMP SCI IEE
[3] BATU T, 2003, P S THEOR COMP ACM N
[4] Broder A. Z., 1997, P 6 INT WORLD WID WE, V29, P1157, DOI [DOI 10.1016/S0169-7552(97)00031-7, 10.1016/S0169-7552(97)00031-7]
[5] Cormode G, 2002, SIAM PROC S, P667
[6] CORMODE G, 2000, P S FDN COMP SCI IEE
[7] Indyk P., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P604, DOI 10.1145/276698.276876
[8] INDYK P, 1930, P S FDN COMP SCI IEE, P646
[9] KRAUTHGAMER R, 2006, P ACM SIAM S DISCR A
[10] Efficient search for approximate nearest neighbor in high dimensional spaces
Kushilevitz, E
Ostrovsky, R
Rabani, Y
[J]. SIAM JOURNAL ON COMPUTING, 2000, 30 (02) : 457 - 474

← 1 2 →