Using Pivots to Index for Support Vector Machine Queries

Arun Qamra, University of California Santa Barbara
Edward Y. Chang, University of California Santa Barbara

In many data-mining applications, Support Vector Machines are used to learn query concepts, and then the learned SVM is used to find the corresponding best matches in a given dataset. When the dataset is large, naively scanning the entire dataset to find the instances with the highest classification scores is not practical. An indexing strategy is thus desirable for scalability. In contrast to queries in traditional similarity search scenarios which are in the form of an input space point, SVM queries are hyperplanes in a (kernel function induced) feature space, and the best matches are instances farthest from the hyperplane. Also, the kernel parameters used, and hence the feature space used, may vary with the query. These issues make the problem challenging. In this work, we propose an indexing strategy that uses pivots (selected using PCA or KPCA) to prune irrelevant instances from the dataset, and zoom in on a smaller candidate set, to efficiently answer SVM queries.