Low distortion embeddings for edit distance

DOI10.1145/1284320.1284322zbMath1326.68327OpenAlexW1968570655MaRDI QIDQ5900522

Rafail Ostrovsky, Yuval Rabani

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1284320.1284322

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Information storage and retrieval of data (68P20)

Related Items (8)

Sketching and Embedding are Equivalent for Norms ⋮ Unnamed Item ⋮ Representation and coding of signal geometry ⋮ Unnamed Item ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Index structures for fast similarity search for symbol strings ⋮ Unnamed Item

This page was built for publication: Low distortion embeddings for edit distance