A wide range of face appearance variations can be modeled by using set-based recognition approaches effectively, but computational complexity of current methods is highly dependent on the set and class sizes. This paper introduces new video-based classification methods designed for reducing the required disk space of data samples and speed up the testing process in large-scale face recognition systems. In the proposed method, image sets collected from videos are approximated with kernelized convex hulls and it was shown that it is sufficient to use only the samples that participate in shaping the image set boundaries in this setting. The kernelized support vector data description (SVDD) is used to extract those important samples that form the image set boundaries. Moreover, we show that these kernelized hypersphere models can also be used to approximate image sets for classification purposes. Then, we propose a binary hierarchical decision tree approach to improve the speed of the classification system even more. At last, we introduce a new video database that includes 285 people with 8 videos of each person, since the most popular video data sets used for set-based recognition methods include either a few people, or small number of videos per person. The experimental results on varying sized databases show that the proposed methods greatly improve the testing times of the classification system (we obtained speed-ups to a factor of 20) without a significant drop in accuracies.