SPFresh

6 min read

SPFresh is an incremental spatial clustering algorithm used to maintain Inverted File (IVF) vector indexes dynamically as new data is written or deleted.

What SPFresh Is

In traditional vector databases (for ex: Turbopuffer V1), adding large amounts of new data required periodically stopping to re-cluster and re-index the entire dataset from scratch — a process known as "rebuilding the world". SPFresh solves this by allowing cluster boundaries to adapt incrementally in real time, sustaining high write rates (e.g., tens of thousands of writes per second) while preserving search accuracy (recall) and predictable query latencies.

Step-by-Step Example: An E-Commerce Catalog

Imagine an e-commerce search engine that converts product descriptions into vector coordinates and groups similar products into spatial clusters.

Step 1: Initial Balanced State

• The database starts with three well-defined product clusters, each represented by a center point called a centroid:
  • Cluster A (Shoes Centroid): Contains 5,000 shoe vectors.
  • Cluster B (Dresses Centroid): Contains 5,000 dress vectors.
  • Cluster C (Pants Centroid): Contains 5,000 pant vectors.
• When a user searches for "summer footwear", the query engine compares the query against the centroids, identifies Cluster A (Shoes) as the closest match, and scans only that cluster's file.

Step 2: Heavy Write Ingestion (Cluster Overflow)

• The e-commerce store launches a major apparel campaign. Merchants upload 50,000 new dress items (evening gowns, sundresses, mini-dresses, rompers).
• As these new vectors land in the Write-Ahead Log (WAL) and are assigned to their nearest centroid, Cluster B (Dresses) balloons from 5,000 to 55,000 vectors.
• The Problem: Scanning an oversized cluster of 55,000 vectors takes 10× longer, causing query latency spikes for anyone searching for dresses.

Step 3: Incremental Cluster Splitting (SPFresh Triggers)

• Instead of pausing the database to re-cluster all shoes, pants, and dresses from scratch, SPFresh detects that Cluster B has crossed its density/size threshold.
• SPFresh splits Cluster B (Dresses) into two smaller sub-clusters:
  • Cluster B1 (Casual & Short Dresses)
  • Cluster B2 (Formal & Long Gowns)
• SPFresh computes two new local centroids for B1 and B2 without altering the unrelated Shoe or Pants clusters.

Step 4: Boundary Re-assignment & Merging

• Because splitting Cluster B shifts local spatial boundaries, some vectors near the border (like a versatile summer dress) may now sit closer to a neighboring cluster.
• SPFresh locally re-assigns boundary vectors to their true nearest centroid to maintain high search recall.
• (Conversely, if a cluster loses vectors due to deletions, SPFresh can merge adjacent sparse clusters to prevent empty fragment overhead).

Step 5: Writing Incremental SSTables to Object Storage

• The updated cluster files and modified index tree are written out to S3 as new, immutable SSTables (Sorted String Tables) and registered in the namespace manifest.
• Future queries for dresses now hit the smaller, split clusters (B1 or B2), keeping search latency low and recall high.

The Math Behind SPFresh

What Clustering Is Really Doing

An IVF index groups vectors into clusters, each represented by a centroid (the average position of its members). The goal of clustering is just "tight neighborhoods": every vector should sit close to its cluster's centroid. K-Means finds those centroids by minimizing the total squared distance between each vector and its assigned center — but you don't need the formal objective function to grasp it. Close to center = good; far from center = bad.

Why Global Re-clustering Fails at Scale

Rebuilding the index from scratch means comparing every vector against every centroid, over several passes — roughly $N \times K$ distance computations per pass. With 100 million vectors and thousands of clusters, one rebuild is billions of distance calculations. Worse, while the index waits for the next rebuild, popular clusters keep ballooning — and since querying a cluster means scanning it, search latency for that region grows in direct proportion to how bloated the cluster has become.

SPFresh's Trick: Keep the Math Local

SPFresh replaces one giant global problem with four small local rules:

1. Assign: a new vector joins the cluster whose centroid is closest — a plain distance comparison.
2. Split: when a cluster outgrows its size threshold, run a tiny 2-means on just that one cluster — splitting one overfull bucket into two balanced halves.
3. Merge: when deletions leave a cluster nearly empty, combine it with its nearest neighbor. The new centroid is just a size-weighted average of the two old ones.
4. Fix borders: after a split, check the vectors sitting near the boundary in adjacent clusters; if any of them is now closer to a new centroid, move it over.

The key property: every rule touches only the vectors of one cluster. The cost scales with the cluster's size — not the size of the database.

A Tiny Worked Example (2D, By Hand)

Setup: max cluster size (threshold) = 4 vectors. Two centroids: $c_1 = (2, 2)$ and $c_2 = (10, 10)$. Cluster $C_1$ holds three vectors: $(1.5, 2)$, $(2, 2.5)$, and $(2.5, 1.5)$.

A new vector arrives: $(1, 1)$. Distance to $c_1$: $(1-2)^2 + (1-2)^2 = 2$. Distance to $c_2$: $81 + 81 = 162$. Clearly closer to $c_1$ — it joins $C_1$, which now holds 4 vectors.

Another arrives: $(0.5, 1.5)$. Distance to $c_1$: $2.25 + 0.25 = 2.5$ — joins $C_1$, which now holds 5 vectors > threshold of 4. Overflow!

Split $C_1$ locally (2-means on just these 5 vectors):

• $c_{1a} = (1.0,\ 1.5)$ — grouping $(1, 1)$, $(0.5, 1.5)$, $(1.5, 2)$
• $c_{1b} = (2.25,\ 2.0)$ — grouping $(2, 2.5)$, $(2.5, 1.5)$

Note what we didn't do: $c_2$ at $(10, 10)$ was never touched, its vectors were never read, and its file on S3 was never rewritten. Only $C_1$'s data was written out as two new small cluster files.

That's the whole idea in miniature: we fixed a 5-vector problem instead of a 100-million-vector problem — and search over that region is fast again because queries now scan two clusters of ~2–3 vectors instead of one cluster of 5.

Try It Yourself

Step through this exact example — ingest the new vectors, watch the overflow trigger the local split, and see which clusters (and S3 files) are touched:

Summary of Benefits

Related reads

• K-Means Clustering: 2D Vector Example — the clustering behind every split
• Centroid Calculation in K-Means — the math of the new centers SPFresh computes
• SSTables: The Sorted String Table — the immutable files split clusters are written to