Streaming algorithms for embedding and computing edit distance in the low distance regime

DOI10.1145/2897518.2897577zbMath1375.68231OpenAlexW2416529140MaRDI QIDQ5361873

Elazar Goldenberg, Michal Koucký, Diptarka Chakraborty

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

Hamming distancekerneledit distancelow distortionrandomized embeddingdistance between strings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items (6)

Unnamed Item ⋮ Unnamed Item ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Unnamed Item ⋮ Index structures for fast similarity search for symbol strings ⋮ Unnamed Item

This page was built for publication: Streaming algorithms for embedding and computing edit distance in the low distance regime