Nearest-Neighbor based Image Classification (N-NIC) has drawn considerable attention in the past several years because it does not require classifier training. Similar to an orderless Bag-of-Feature image representation, the traditional NNIC ignores global geometric correspondence. In this paper, we present a technique to exploit the global geometric correspondence in a nearest neighbor classifier framework. We divide an image into increasingly fine sub-regions like the Spatial Pyramid Matching (SPM) approach, and introduce a Pyramid Nearest Neighbor Search kernel by measuring the search similarity between a local descriptor and a feature set in each pyramid window. Instead of using a fixed weighting as in SPM, the weights of the pyramid windows are learned in a class-dependent manner. By doing so, we learn a class-specific geometric correspondence. Finally, an optimal nearest neighbor classifier framework is developed to incorporate the kernel functions over different pyramid windows. We evaluate our proposed approach on a number of public datasets, and show the results significantly outperform existing techniques.