liveBook · Manning

Space complexity

As explained in Build AI Drug Discovery Pipelines

Memory complexity is an asymptotic measure of the memory required by an algorithm as input size grows.

Space complexity measures how an algorithm’s memory requirements grow as input size increases. For molecular clustering, the dominant storage structure can determine whether a method scales to a compound library. section 7.2.3

For clustering molecular fingerprints:

  • Agglomerative clustering uses O(n²) memory for its pairwise distance matrix. section 7.2.3
  • K-means uses O((n + k) × d) memory to store data points and centroids. section 7.2.3
  • Taylor-Butina uses O(n²) memory when the implementation materializes all pairwise distances, but an optimal implementation can use O(n × d). section 7.2.3

Molecular library clustering

With n compounds and d fingerprint dimensions, storing every pairwise distance requires quadratic memory, while storing compounds and their features requires linear-in-n memory. section 7.2.3

Listing 7.7 Fit Agglomerative Clustering with Ward’s Method
from rdkit import DataStructs
from rdkit.Chem import rdFingerprintGenerator
from sklearn.cluster import AgglomerativeClustering
 
def molecules_to_fingerprints(mols, maxPath=5):
    rdkit_gen = rdFingerprintGenerator.GetRDKitFPGenerator(    #A
        maxPath=maxPath)   #A
    fingerprints = [rdkit_gen.GetFingerprint(mol) for mol in mols]
    np_fps = []
    for fp in fingerprints:
        arr = np.zeros((1,))
        DataStructs.ConvertToNumpyArray(fp, arr)
        np_fps.append(arr)
    return np.array(np_fps), fingerprints
 
fps, rdkit_fps = molecules_to_fingerprints(new_mols)
 
model = AgglomerativeClustering(    #B
    distance_threshold=0, n_clusters=None, linkage='ward')    #B
model = model.fit(fps)

Inspect fingerprint conversion and agglomerative clustering code to connect the memory analysis with a molecular implementation. section 7.2.3

How Build AI Drug Discovery Pipelines covers it

How deep it goes
Derives worst-case memory bounds for three clustering algorithms and contrasts materialized versus optimal Taylor-Butina implementations.
Examples
Uses pairwise distance matrices, centroids, molecular fingerprints, and RDKit clustering implementations as concrete memory examples.
What it assumes
Assumes familiarity with data points, dimensions, iterations, centroids, and molecular fingerprints while defining their roles in complexity expressions.
What you can do after
Evaluate memory demands and identify when pairwise-distance materialization creates a quadratic scaling bottleneck.
How it connects
Connects memory complexity with agglomerative clustering, K-means clustering, Taylor-Butina clustering, molecular fingerprints, and time complexity.

Also explained in

Compare how 5 books explain space complexity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Build AI Drug Discovery Pipelines. The section links point to the parts of the book it draws on.