The k-nearest neighbors (k-NN) classification rule has proven extremely
successful in countless many computer vision applications. For example, image
categorization often relies on uniform voting among the nearest prototypes in
the space of descriptors. In spite of its good properties, the classic k-NN
rule suffers from high variance when dealing with sparse prototype datasets in
high dimensions. A few techniques have been proposed to improve k-NN
classification, which rely on either deforming the nearest neighborhood
relationship or modifying the input space.