Why does agglomerative clustering fail on 200,000 rows, and what would you do instead?
answer
- cost grows with the square of rows
- roughly twenty billion pairs here
- hundreds of gigabytes of distances
- sample, summarise, or restrict merges
- each workaround changes the answer
basics
~20 sAgglomerative clustering needs distances between all pairs: 200,000 rows means about 20 billion pairs, roughly 160 GB at 8 bytes each. Practical routes are subsampling and assigning the rest, clustering micro-cluster centroids, or restricting merges to a neighbour graph.
solid answer
~50 sThe blocker is the pairwise distance matrix. With 200,000 rows there are about 2 x 10^10 distinct pairs, so even storing only the upper triangle at 8 bytes per value needs roughly 160 GB, and time is quadratic at best — the naive implementation is cubic, careful ones reach `O(n^2)` — which is still tens of billions of distance evaluations. Three routes work. Subsample: build the tree on 20,000 rows, cut it, then assign the remaining rows to their nearest resulting cluster. Two-stage: run a cheap centroid pass to get a few thousand micro-clusters, then run the hierarchy over those centroids, weighted by their sizes. Or impose a connectivity constraint so merges are only allowed between neighbours in a sparse nearest-neighbour graph, which drops memory to roughly linear. Each changes the answer, so I say which one I used.
go deeper
Know the headline fact: hierarchical clustering needs the distance between every pair of rows, so the memory it needs grows with the square of the row count and large data sets simply do not fit.
Be able to do the arithmetic out loud — pairs, bytes, gigabytes — and to separate the memory cost from the time cost, including that careful implementations reach quadratic time but the matrix is still the binding constraint.
Show that you have actually shipped around this: stratified subsampling with repeated draws, a micro-cluster first pass, or a sparse connectivity constraint, and be explicit about which of these changes the resulting clusters rather than merely the cost.
Own the prior question of whether a hierarchy is the right deliverable at this scale. Its value is exploratory breadth, and the top few splits are already well estimated from a sample, so argue for a cheap recurring method plus a sampled tree as a diagnostic.
## Where the wall is Agglomerative clustering is defined over the distances between all current clusters, and at the first step every observation is its own cluster. For `n = 200,000`: - distinct pairs: `n * (n - 1) / 2` is about `2 x 10^10` - at 8 bytes per distance, the condensed upper triangle is about **160 GB** (the full square matrix about 320 GB) That is the memory wall, and it is hard: no amount of patience gets around it, and the quadratic growth means halving `n` only quarters the requirement. Going from 200,000 to 20,000 rows brings it to roughly 1.6 GB, which is why subsampling is the first thing anyone reaches for. Time is the second constraint. The naive implementation — rescan every pair after every merge — is `O(n^3)`. Priority-queue implementations reach `O(n^2 log n)`. For linkages that satisfy the reducibility property (single, complete, average and Ward all do), the nearest-neighbour-chain algorithm attains `O(n^2)` time with only `O(n)` extra memory, and single linkage in particular is equivalent to computing a minimum spanning tree, which can be done in `O(n^2)` time with linear memory. But `O(n^2)` at `n = 200,000` is still on the order of `10^10` distance computations — hours, not seconds — and the memory-light variants give you the tree, not a stored distance matrix you can inspect. ## What to do instead **1. Subsample and extend.** Draw a stratified sample of 20,000 to 50,000 rows, build the full tree, cut it, then assign every remaining row to the nearest cluster by its centroid or its nearest sampled member. This preserves the exploratory value of the dendrogram and is usually the right first move. The cost is that groups too rare to appear in the sample are invisible, so stratify on anything you already know matters, and repeat with several samples to see whether the same branches keep appearing. **2. Two-stage clustering.** Run a cheap centroid-based pass over all rows to produce many micro-clusters — a few thousand, deliberately far more than the structure you expect — then build the hierarchy over those centroids, weighting each by the number of rows it represents. Every row is represented, memory drops to the square of the micro-cluster count, and the tree still reflects the whole data set. The tradeoff is that the first pass fixes what can never be separated afterwards: two genuinely distinct groups pooled into one micro-cluster stay pooled. Using many more micro-clusters than you need is the mitigation. Streaming summarisation methods such as BIRCH formalise this idea, summarising the data into a compact tree of cluster features in a single pass and running the hierarchy on those summaries. **3. Constrain the merges.** Supply a sparse connectivity structure — for instance a k-nearest-neighbour graph — and permit merges only between clusters that touch in that graph. Memory becomes about `O(n * k)` rather than `O(n^2)`. This is the least well understood of the three, because it changes the result and not just the cost: merges become locally constrained, so the method behaves more like connected-component growth, elongated clusters become easier to find, and if the graph has disconnected components you cannot merge below their number, so you may get more clusters than you asked for. ## Framing the decision The question behind the question is whether you need a hierarchy at all. The dendrogram earns its quadratic cost when the deliverable is exploratory: a picture that shows every granularity at once for people who have not committed to a number of groups. If what you actually need is one partition at a known granularity on a recurring schedule, a method with linear or near-linear cost in the number of rows is the better tool, and the hierarchy is a one-off diagnostic you build on a sample. Also worth stating plainly in a design discussion: the greedy, no-undo nature of the merge sequence means that on a very large data set the upper tree is decided by a very long chain of local decisions. Scaling agglomerative clustering to hundreds of thousands of rows buys precision in the merge order that nobody will ever look at, while the part people do look at — the top few splits — is exactly the part a well-drawn sample already estimates well.
- How does a nearest-neighbour connectivity constraint change the clusters, not just the cost?It forbids merges between clusters that are not neighbours in the graph, so merging becomes local. Elongated and curved clusters become much easier to recover, results depend on the neighbour count you chose, and if the graph splits into disconnected components you cannot merge below that number of clusters — so you may be handed more clusters than you asked for.
- Why is single linkage the cheapest of the four rules at scale?Single-linkage clustering is equivalent to building a minimum spanning tree: the merge heights are exactly the MST edge weights in increasing order. That can be computed in quadratic time with only linear extra memory, so no distance matrix ever has to be stored. It buys memory, not immunity from chaining.
- In the two-stage approach, how many micro-clusters would you ask the first pass for?Far more than the structure you expect — a few thousand for a data set of this size, even if you anticipate under ten final groups. The first pass fixes what can never be separated later, so over-partitioning is the cheap side of the error. The only cost is the hierarchy over that many centroids, which is trivial by comparison.
Insisting on the full tree for 200,000 rows is like demanding a seating chart that lists the distance between every pair of guests before anyone may sit down.
saying these in an interview costs you the question
- Thinks the problem is only slow runtime, not memory
- Believes a faster machine removes a quadratic memory wall
- Subsamples without stratifying or repeating the draw
- Presents a connectivity-constrained tree as the unconstrained one
- Assumes an O(n^2) algorithm makes 200,000 rows comfortable