Finding matching images of a person from large-scale databases efficiently and quickly is still a difficult challenge in face-image retrieval. Most of the existing systems cannot scale with the ever-increasing size of image databases or suffer from a loss in accuracy introduced due to an approximate search. Therefore, this research study proposes a novel indexing method using a hierarchy of classifiers that predict attributes such as age, gender, and ethnicity on which the database is indexed through a hash table. Only a small subset of the database is selected from the indexed hash table for the matching process, thereby reducing retrieval time while simultaneously maintaining low computational complexity. The hierarchical classifiers are trained using transfer learning with a pre-trained convolutional neural network. To minimize the classification error introduced by the classifiers, a novel probabilistic back-tracking algorithm is proposed that rectifies miss-classifications using conditional probabilities. Another method, dynamic thresholding, is proposed that dynamically sets a threshold for matching computations based on the predicted attributes. Rigorous testing of classifiers was conducted to assess their performance, which shows comparable results with state-of-the-art methods. Experimental evaluation of the proposed indexing strategy under hard tests on a large-scale database demonstrates a significant reduction in retrieval time and a considerable increase in retrieval accuracy over existing methods for face-image retrieval. Finally, statistical tests prove the importance of the proposed probabilistic back-tracking algorithm and the dynamic thresholding technique.