Florian Weimer <fw(at)deneb(dot)enyo(dot)de> writes:
> http://citeseer.ist.psu.edu/1593.html suggests that this uninteresting
> (too much of the database is examined) once you go past an edit distance
> of 1. I don't know if this is a problem in your case (it is in mine).
Did you see the test results in bk-tree[1] project? Results will
change with respect to metric distance distribution of your input
data, but I was quite impressed by the numbers when I first saw them.
[1] http://www.cliki.net/bk-tree
Regards.