For those who are interested: I've updated the cookbook tutorial on the kd-tree: http://scipy.org/Cookbook/KDTree It now also includes parallel search for multicore CPUs (multiprocessing standard module). Even if you are not genuinely interested in kd-trees, it shows how to do parallel processing in Python despite of the GIL.