A completely different approach to the problem is to minimize the number of necessary distance computation in the first place. There are various indexing algorithms which make finding nearest neighbours feasible in large datasets. Incidentally, I implemented two of them. :)

http://well-adjusted.de/mspace.py

For real usage, you would probably want to reimplement them with performance in mind (and in a different language), though. My implementation is dog slow. But on the plus side, it is very readable and heavily documented.