Exact indexing for support vector machines

Hwanjo Yu, Ilhwan Ko, Youngdae Kim, Seungwon Hwang, Wook Shin Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)


SVM (Support Vector Machine) is a well-established machine learning methodology popularly used for classification, regression, and ranking. Recently SVM has been actively researched for rank learning and applied to various applications including search engines or relevance feedback systems. A query in such systems is the ranking function F learned by SVM. Once learning a function F or formulating the query, processing the query to find top-k results requires evaluating the entire database by F. So far, there exists no exact indexing solution for SVM functions. Existing top-k query processing algorithms are not applicable to the machine-learned ranking functions, as they often make restrictive assumptions on the query, such as linearity or monotonicity of functions. Existing metric-based or reference-based indexing methods are also not applicable, because data points are invisible in the kernel space (SVM feature space) on which the index must be built. Existing kernel indexing methods return approximate results or fix kernel parameters. This paper proposes an exact indexing solution for SVM functions with varying kernel parameters. We first propose key geometric properties of the kernel space - ranking instability and ordering stability - which is crucial for building indices in the kernel space. Based on them, we develop an index structure iKernel and processing algorithms. We then present clustering techniques in the kernel space to enhance the pruning effectiveness of the index. According to our experiments, iKernel is highly effective overall producing 1∼5% of evaluation ratio on large data sets. According to our best knowledge, iKernel is the first indexing solution that finds exact top-k results of SVM functions without a full scan of data set.

Original languageEnglish
Title of host publicationProceedings of SIGMOD 2011 and PODS 2011
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Print)9781450306614
Publication statusPublished - 2011
Event2011 ACM SIGMOD and 30th PODS 2011 Conference - Athens, Greece
Duration: 2011 Jun 122011 Jun 16

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Other2011 ACM SIGMOD and 30th PODS 2011 Conference

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems


Dive into the research topics of 'Exact indexing for support vector machines'. Together they form a unique fingerprint.

Cite this