I've used Burkhard-Keller trees to do something like this: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees http://blog.notdot.net/2007/4/Dam

I've used Burkhard-Keller trees to do something like this: 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... I don't know off the top of my head which one is more efficient.