sturlamolden: > It seems we have been implementing different algorithms. kd-trees are > not BK-trees. > http://www.scipy.org/Cookbook/KDTree Sorry for my silly mistake :-) Note: in your code I don't know if the collections.deque data structure may help (it's faster than list for appending), but I presume that's not a bottleneck. Bye, bearophile