This paper addresses the problem of face retrieval on large datasets by proposing an efficient representation for face videos. In comparison to the classical face verification problem, face retrieval poses additional challenges originating from database size. First, a different characteristic of recognition performance is required because retrieval scenarios have only very few correct face samples embedded in a large amount of imposters. In addition, the large number of samples in the database requires fast matching techniques. In this contribution, we present a face retrieval system which addresses these challenges. The first step consists of a set of measures to reduce frame descriptor dimension which saves processing time while keeping recognition performance. Afterwards, a novel Pyramid Mean Representation (PMR) of face videos is presented which allows for fast and accurate queries on large databases. The key concept is a hierarchical data representation with increasing sparsity which is used for an iterative query evaluation in a coarse to fine manner. The effectiveness of the proposed system is evaluated on the currently largest and most challenging public dataset of unconstrained videos, the YouTube Faces Database. In addition to the official verification test protocol, we define a protocol for face retrieval using a leave-oneout strategy. The proposed system achieves the best performance in this protocol with less processing time than baseline methods.