1. A method for recognizing a face, comprising: receiving images of training faces; generating feature vectors of the images; generating clusters from the feature vectors each with one or more centroids or a cluster representative; for a query to search for a query face, generating query feature vectors for the query face and comparing the query feature vectors with the centroids of all clusters to find one or more similar clusters; for clusters above a similarity threshold, comparing feature vectors of corresponding members of the clusters with the query feature vectors; and indicating as matching candidates for cluster members with similarity above a threshold, wherein each cluster model size is sub-linear or logarithmic in the number of the training faces (or features) in a database.