The next course of action would be to split your distance calculation into multiple steps - a few dimensions at a time.

Then we need to decide on an order to these comparisons - what about using entropy derived from the training data?

Then as a further improvement, what if the order need not be constant, depending on which group the data point is closer to? And what if not all dimensions need to be considered?

Before you know it, woah! You've reinvented trees!

This comment is meant as a joke