Abstract: This paper proposes a novel cluster-based face image retrieval algorithm. By using normalized cuts (NCuts) to cluster faces in each time span into optimal partitions, various face images of the same character can be grouped together. A face recognition classifier learned by real AdaBoost is used for measuring similarity between two faces, and a similarity measure for the query face and the face cluster is further proposed for retrieval. To further improve the performance, we design an online step, in which users can interactively label false positives and missing retrieval, so that some constraints are involved to revise the clustering results. The algorithm is integrated into an automatic retrieval system, and the experiment on a family album containing over a thousand face images confirms its effectiveness in comparison to other alternative algorithms.