Substructures are among the most preferred molecular descriptors in chemoinformatics and medicinal chemistry. Conventional substructure-type descriptors are typically the result of well-defined design strategies. Previously, we have introduced Activity Class Characteristic Substructures (ACCS) derived from randomly generated molecular fragment populations and described their utility in similarity searching. Short ACCS fingerprints were found to perform surprisingly well on many compound classes when compared to more complex state-of-the-art 2D fingerprints. In order to elucidate potential reasons for the high predictive utility of ACCS, we have carried out a thorough analysis of their distribution in nine activity classes and nearly four million database compounds. We show that the discriminatory power of ACCS results from the rare occurrence of ACCS combinations in screening databases.