This chapter presents an efficient Support Vector Machine (eSVM) for image search and video retrieval in general and accurate and efficient eye search in particular. Being an efficient and general learning and recognition method, the eSVM can be broadly applied to various tasks in intelligent image search and video retrieval. The eSVM first defines a θ set that consists of the training samples on the wrong side of their margin derived from the conventional soft-margin SVM. The θ set plays an important role in controlling the generalization performance of the eSVM. The eSVM then introduces only a single slack variable for all the training samples in theθ set, and as a result, only a very small number of those samples in the θ set become support vectors. The eSVM hence significantly reduces the number of support vectors and improves the computational efficiency without sacrificing the generalization performance. The optimization of the eSVM is implemented using a modified Sequential Minimal Optimization (SMO) algorithm to solve the large Quadratic Programming (QP) problem. A new eye localization method then applies the eSVM for accurate and efficient eye localization. In particular, the eye localization method consists of the eye candidate selection stage and the eye candidate validation stage. The selection stage selects the eye candidates from an image through a process of eye color distribution analysis in the YCbCr color space. The validation stage applies first 2D Haar wavelets for multi-scale image representation, then PCA for dimensionality reduction, and finally the eSVM for classification. Experiments on several diverse data sets show that the eSVM significantly improves the computational efficiency upon the conventional SVM while achieving comparable classification performance with the SVM.Furthermore, the eye localization results on the Face Recognition Grand Challenge (FRGC) database and the FERET database reveal that the proposed eye localization method achieves real-time eye detection speed and better eye detection performance than some recent eye detection methods.