Abstract The development of complex, powerful classififiers and their constant improvement have contributed much to the progress in many fifields of computer vision. However, the trend towards large scale datasets revived the interest in simpler classififiers to reduce runtime. Simple nearest neighbor classififiers have several benefificial properties, such as low complexity and inherent multi-class handling, however, they have a runtime linear in the size of the database. Recent related work represents data samples by assigning them to a set of prototypes that partition the input feature space and afterwards applies linear classififiers on top of this representation to approximate decision boundaries locally linear. In this paper, we go a step beyond these approaches and purely focus on 1-nearest prototype classififi- cation, where we propose a novel algorithm for deriving optimal prototypes in a discriminative manner from the training samples. Our method is implicitly multi-class capable, parameter free, avoids noise overfifitting and, since during testing only comparisons to the derived prototypes are required, highly effificient. Experiments demonstrate that we are able to outperform related locally linear methods, while even getting close to the results of more complex classififiers.