Organizing digital images into semantic categories is imperative for effective browsing and retrieval. In large image collections, efficient algorithms are crucial to quickly categorize new images. In this paper, we study a nearest neighbor based algorithm in image classification from a different perspective. The proposed algorithm vertically decomposes image features into separate bit vectors, one for each bit position of the values in the features, and approximates a number of candidates of nearest neighbors by examining the absolute difference of total variation between the images in the repositories and the unclassified image. Once the candidate set is obtained, the k-nearest neighbors are then searched from the set. We use a combination of global color histogram in HSV (6x3x3) color space and Gabor texture for the image features. Our experiments on Corel dataset show that our algorithm is fast and scalable for image classification even when image repositories are very large. In addition, the classification accuracy is comparable to the accuracy of the classical KNN algorithm.