You know, non-parametric methods along the lines of k-nearest neighbors basically do this. The cleverness in these methods is finding a log(n) access scheme for your data (a database problem, essentially, rather than a machine learning problem).