When, if ever, is nearest neighbor classification the best choice? I've been researching the history and use of k-nearest neighbor classification and regression, and various tweaks including k-d trees and LAESA. 

I understand that it is useful because it is simple and flexible, but can be computationally expensive and requires a lot of data storage.

But here's what I don't know:


  Is there any class of problems for which nearest neighbor classification is the best or one of the best algorithms to use?


By 'class of problems' I mean either a class based on data structure (for instance, maybe KNN is great for low-dimensional data with a mix of nominal and numerical data), or a class of real-life problems (maybe KNN is useful in predicting diseases for insurance holders).
One situation where NN would be ideal is if the data are sample points of a piecewise constant function. In this case, the true function is composed of a tesselation of its domain, with a constant value for all points within each division.