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. -- http://mail.python.org/mailman/listinfo/python-list
