skip to main content
10.1145/1160939.1160954acmotherconferencesArticle/Chapter ViewAbstractPublication PagescvdbConference Proceedingsconference-collections
Article

Using pivots to index for support vector machine queries

Published: 17 June 2005 Publication History

Abstract

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.

References

[1]
M. Brown, W. Grundy, D. Lin, N. Christianini, C. Sugnet, M. Jr, and D. Haussler. Support vector machine classification of microarray gene expression data. 1999.
[2]
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/cjlin/libsvm.
[3]
E. Chang, K. Goh, G. Sychay, and G. Wu. Content-based soft annotation for multimodal image retrieval using bayes point machines. IEEE Trans. on Circuits and Systems for Video Technology Special Issue on Conceptual and Dynamical Aspects of Multimedia Content Description, 13(1):26--38, 2003.
[4]
Edward Chang and Simon Tong. Svm Active - support vector machine active learning for image retrieval. Proceedings of the ninth ACM international conference on Multimedia, pages 107--118, 2001.
[5]
P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. Proc. 23rd Int. Conf. on Very Large Databases, pages 426--435, 1997.
[6]
J. T. Kwok and I. W. Tsang. The pre-image problem in kernel methods. In Proceedings of ICML-03, 20th International Conference on Machine Learning, pages 408--415, 2003.
[7]
D. A. Keim. Tutorial on high-dimensional index structures: Database support for next decades applications. In Proceedings of the International Conference on Data Enginnering, 2000.
[8]
S. Mika, B. Scholkopf, A. Smola, K. R. Muller, M. Scholz, and G. Ratsch. Kernel pca and de-noising in feature spaces. Advances in Neural Information Processing Systems, 11:536--542, 1999.
[9]
N. Panda and E. Y. Chang. Exploiting geometric property for support vector machine indexing. In SIAM International Conference on Data Mining (SDM), 2005.
[10]
J. Peng and D. R. Heisterkamp. Kernel indexing for relevance feedback image retrieval. Proceedings of IEEE International Conference on Image Processing (ICIP-2003), 1:733--736, 2003.
[11]
V. Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, 1995.
  1. Using pivots to index for support vector machine queries

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    CVDB '05: Proceedings of the 2nd international workshop on Computer vision meets databases
    June 2005
    75 pages
    ISBN:1595931511
    DOI:10.1145/1160939
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 17 June 2005

    Permissions

    Request permissions for this article.

    Check for updates

    Qualifiers

    • Article

    Conference

    CVDB05

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 158
      Total Downloads
    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 17 Feb 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media