Efficient approximate classification with support vector machines and index structures in the input space

We propose an approach to efficiently and effectively identify, in very large datasets, the best elements belonging to classes defined using Support Vector Machines (top-k classification). The proposed approach leverages on techniques of efficient similarity searching to identify a subset of candidate elements for a class, substantially smaller than the original dataset. Thus, the decision function, associated with a class, needs to be applied to the elements in the candidate set, rather than to all elements of the dataset, dramatically reducing the needed cost. Given that it might happen that some qualifying elements are not included in the candidate set, the result is an approximation of the exhaustive classification. We show that the proposed approach is order of magnitude faster than exhaustive classification, still providing an high degree of accuracy.