Approximating edit distance in near-linear time
Authors:
Open Access
- 31 May 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 199-204
Abstract
No abstract availableKeywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Low distortion embeddings for edit distanceJournal of the ACM, 2007
- Stable distributions, pseudorandom generators, embeddings, and data stream computationJournal of the ACM, 2006
- Nonembeddability theorems via Fourier analysis2005
- Approximating Edit Distance Efficiently2004
- A sublinear algorithm for weakly approximating edit distance2003
- A guided tour to approximate string matchingACM Computing Surveys, 2001
- AnO(ND) difference algorithm and its variationsAlgorithmica, 1986
- On lipschitz embedding of finite metric spaces in Hilbert spaceIsrael Journal of Mathematics, 1985
- A faster algorithm computing string edit distancesJournal of Computer and System Sciences, 1980