Levenshtein distance is a metric [1] and discrete metrics can be indexed with BK trees, taking advantage of the triangle inequality. For a detailed explanation,

Levenshtein distance is a metric [1] and discrete metrics can be indexed with BK trees, taking advantage of the triangle inequality. For a detailed explanation, see [2]. I know of no real world implementation of this, however. [1] https://en.wikipedia.org/wiki/Metric_(mathematics) https://en.wikipedia.org/wiki/Metric_(mathematics) [2] http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK...