Building a live ANN index on object storage

Give each vector a home

Nearby vectors are grouped around a representative centre, or centroid. A query can then visit a few promising groups instead of searching the whole collection. Good placement matters: a true neighbour in a group the query skips is lost before scoring begins.

Our implementation, Cellstore, calls each group a cell. We train centroids on a sample and assign every vector one home cell (R = 1), aiming for its nearest centroid. That same cell becomes the unit we search and repair.

Routing works in two levels. A small set of super-centroids groups the cells; a query chooses promising groups, then selects cells within them. We keep this routing information in memory, so the query can decide where to look before reading the candidate data.

The design builds on partition-based search in SPANN and local partition maintenance in SPFresh, adapted to an index stored as immutable objects.

Spend reads on promising candidates

Choosing a few cells still leaves many vectors to compare. Each vector has a compact binary code for a cheap first pass and a separate full-vector representation for rescoring. The scan keeps a shortlist; full-vector scores determine its final order.

This separation matters on object storage. The query first reads codes from the selected cells, then fetches vectors for the shortlist. We batch related reads and cache frequently used data. A query pays for the regions and candidates it explores, rather than pulling every vector in those regions through the expensive scoring path.

Searching more cells or keeping a longer shortlist can recover more neighbours, at the cost of more work. Rescoring only helps candidates that survive the earlier stages, so we measure the quality of routing and code filtering as well as the final results.

Keep the partition useful as it changes

As vectors arrive and disappear, cell sizes and assignments become uneven. Crowded cells make queries scan more candidates; poor placement can hide useful neighbours. Maintenance repairs the affected regions so the partition continues to serve the search path.

A split also changes its neighbourhood

When a cell grows too large, we split it into two smaller cells. Their new centroids may be better homes for vectors in nearby cells too. We revisit those neighbours and move eligible vectors, repairing the boundary as well as the original cell.

Nearby splits share a repair pass, so overlapping neighbourhoods are handled together. The amount of neighbourhood work is a quality tradeoff: too little can leave vectors in poor homes. Placement needs to be checked over repeated updates.

Retire a cell after moving its survivors

Deletes can leave a cell too sparse to keep. We reassign its surviving vectors to nearby cells, potentially to different destinations, before retiring it. Every live vector keeps one home; a move removes the old membership and installs the new one in the same index version.

Publish a coherent view, then clear the history

Updates are recorded before background work folds them into the partition. Readers incorporate recent changes as they catch up, while maintenance prepares the next durable version of the index.

Existing objects remain immutable. The writer prepares new data and matching routing information, then publishes the version once its parts are ready. Each query holds one consistent view; later queries can adopt the new version without interrupting work already in flight.

Small incremental writes leave a history of additions and deletions. Background compaction consolidates that history so future queries have fewer pieces to read. Compaction itself rewrites data, so its cadence balances maintenance cost against the extra work carried by queries.

Local repair and compaction address different kinds of drift: one keeps the geometry useful, while the other keeps accumulated history from slowing down the read path.

Track quality and cost through updates

A live index needs to be evaluated throughout its lifetime. We track three things together:

1. Search quality.

   Compare results with exact nearest neighbours. Check whether routing and compact codes retain useful candidates as the vector distribution changes.

2. Placement.

   Measure how many vectors remain in their nearest-centroid cell after repeated inserts and deletes. Being present exactly once is a separate property from being placed well.

3. Work over time.

   Track query latency, data read, and maintenance writes as updates accumulate. These show when local repair or compaction is falling behind.

On our 8.84-million-vector evaluation corpus, the finer partition reached 93.6% ANN Recall@10 at 7.55 ms warm median latency on one CPU core. The curves compare our two partition sizes with LanceDB on the same vectors and queries.

In a separate update check, we added one million duplicate vectors under new row IDs to the finer partition. At unchanged query settings, recall stayed close, from 88.5% to 88.1%, while warm median latency rose from 3.50 to 5.76 ms before compaction. The index absorbed those additions incrementally; the extra query work shows why maintaining the read path remains part of the job.