document: The IOC algorithm : efficient many-class non-parametric classification for high-dimensional data This paper is about a variant of k nearest neighbor classification on large many-class high dimensional datasets . K nearest neighbor remains a popular classification technique , especially in areas such as computer vision , drug activity prediction and astrophysics . Furthermore , many more modern classifiers , such as kernel-based Bayes classifiers or the prediction phase of SVMs , require computational regimes similar to k-NN . We believe that tractable k-NN algorithms therefore continue to be important . This paper relies on the insight that even with many classes , the task of finding the majority class among the k nearest neighbors of a query need not require us to explicitly find those k nearest neighbors . This insight was previously used in ( Liu et al. , 2003 ) in two algorithms called KNS2 and KNS3 which dealt with fast classification in the case of two classes . In this paper we show how a different approach , IOC ( standing for the International Olympic Committee ) can apply to the case of n classes where n ) 2 . IOC assumes a slightly different processing of the datapoints in the neighborhood of the query . This allows it to search a set of metric trees , one for each class . During the searches it is possible to quickly prune away classes that can not possibly be the majority . We give experimental results on datasets of up to 5.8 x 105 records and 1.5 x 103 attributes , frequently showing an order of magnitude acceleration compared with each of ( i ) conventional linear scan , ( ii ) a well-known independent SR-tree implementation of conventional k-NN and ( iii ) a highly optimized conventional k-NN metric tree search .
doc_bio_tags: O O O O O O O B O O O O O O O O O O B I I B O O O O O O O B I I O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O