Determination of structural similarities between protein binding pockets is an important challenge in in silico drug design. It can help to understand selectivity considerations, predict unexpected ligand cross-reactivity, and support the putative annotation of function to orphan proteins. To this end, Cavbase was developed as a tool for the automated detection, storage, and classification of putative protein binding sites. In this context, binding sites are characterized as sets of pseudocenters, which denote surface-exposed physicochemical properties, and can be used to enable mutual binding site comparisons. However, these comparisons tend to be computationally very demanding and often lead to very slow computations of the similarity measures. In this study, we propose RAPMAD (RApid Pocket MAtching using Distances), a new evaluation formalism for Cavbase entries that allows for ultrafast similarity comparisons. Protein binding sites are represented by sets of distance histograms that are both generated and compared with linear complexity. Attaining a speed of more than 20 000 comparisons per second, screenings across large data sets and even entire databases become easily feasible. We demonstrate the discriminative power and the short runtime by performing several classification and retrieval experiments. RAPMAD attains better success rates than the comparison formalism originally implemented into Cavbase or several alternative approaches developed in recent time, while requiring only a fraction of their runtime. The pratical use of our method is finally proven by a successful prospective virtual screening study that aims for the identification of novel inhibitors of the NMDA receptor.