## 2 Results and Discussion
### Methods
#### 2.1.3 Memory usage and scaling  
The results of clustering for every similarity threshold are stored in memory as an integer number for each chemical structure. Structures with identical numbers belong to the same cluster. Estimated memory requirements to run clustering are:  
1. Dictionary of fragments: 12*\(F\) bytes, where \(F\) is the number of different structural fragments in the database. The number of fragments depends upon diversity of database. For 2M database the typical value of \(F\) is about of 700,000  
2. The centroid vectors of weights and sorted dictionary: 16*\(F\) bytes. 3. Molecular screens as indexes in glossary: 4*\(N\)*\(AvgFrag\)+4*\(N\) bytes. Here \(N\) - the number of chemical structures, \(AvgFrag\)-average number of fragments per compound, which is equal to 35 for databases under study. Screens are stored in linear array; the number of screens for each chemical structure is also stored. 4. Results of clustering: 4*\(N\)*\(N\)st bytes. These memory requirements should be treated as minimal because of a lot of memory is used for auxiliary information (addresses of binary records with chemical structures, tree view graphical control etc.). One should note linear growth of resources used with the database size. To estimate the overall processing, we assume that each cluster is divided into \(k\) cluster uniformly at each similarity threshold. Single cluster exists at similarity threshold 0, while for last threshold (\(Nst\) threshold level, similarity=1) there exist \(N\) clusters. So, \(k\)=exp(ln(\(N\))/\(Nst\)) and the number of clusters at each \(i\)-th level (\(i\)=0..\(Nst\)) is \(m_{i}\)=\(k^{i}\)=exp(ln(\(N\))*\(i\)/\(Nst\)). The size of the \(i\)-th threshold is \(d_{i}\)=\(N\)/\(k^{i}\)=exp(ln(\(N\))*(\(Nst\)-\(i\))/\(Nst\)). Both \(k\) and \(d_{i}\) depend not exponentially, but almost linearly on the dataset size \(N\). The centroid vector is calculated for each cluster, which requires \(d_{i}\)*\(AvgFrag\) additions. The distance of each compound from centroid (scalar product) is calculated, it includes \(d_{i}\)*\(AvgFrag\) multiplications and \(d_{i}\)*\(AvgFrag\) additions. The advantage of non-zero components store should be pointed out. The centroid vector (\(F\)) has large dimensions (hundreds of thousands of components), though, taking into considerations non-zero elements (\(AvgFrag\)) only, it amounts to some tens components. The calculation time is proportional to the i-th cluster size \(d_{i}\) and the average number of nonzero screens equals to \(d_{i}\)*\(AvgFrag\). Subsequent operations are: quick sorting of distances (calculation time is proportional to \(d_{i}\)*ln(\(d_{i}\))), putting the first compound in probe set \(S\), and then selection of most diverse \(k\)-\(I\) compounds. It should be noted, that modifications [29] were implemented for compounds selection, namely:  
Indexes in glossary (their number equals \(AvgFrag\)) are used for fast scalar product calculation  
For selection of the most diverse compounds from cluster to already selected ones in probe set \(S\) it is enough to calculate similarity of few first compounds at the beginning of sorted array only. The number of structures, for which similarities are calculated, is proportional to ln(\(d_{i}\)), therefore the total time for selecting first diverse \(k\) compounds is proportional to \(k\)*ln(\(d_{i}\))*\(AvgFrag\). To assign remaining compounds to \(k\) clusters, scalar products for each remaining (\(d_{i}\)-\(k\)) compounds are calculated with \(k\) probes. The calculation time is proportional to (\(d_{i}\)-\(k\))*\(k\)*\(ln(d_{i})\)*\(AvgFrag\). This procedure is the most time-consuming. Assuming \(d_{i}\)\(>>\)\(k\) (large datasets), the time for single-clusterprocessing is proportional to \(AvgFrag*k*d_{i}*\ln(d_{i})\).