Skip to content

CONCEPT Cited by 1 source

IVF (Inverted File Index)

Definition

IVF (Inverted File index) is a cluster-based approach to approximate nearest-neighbor (ANN) search. The corpus is partitioned into clusters by a coarse quantizer (typically k-means centroids); each cluster owns a posting list of the vectors assigned to it. At query time the search:

  1. Scores the query against the cluster centroids (cheap, in memory);
  2. Selects the top nprobe nearest clusters;
  3. Scans only those clusters' posting lists for the true nearest neighbors.

This is the classic "coarse-quantizer + bucket-scan" family (FAISS IVFFlat, IVFPQ; pgvector's ivfflat), and the structural alternative to graph ANN like HNSW. It trades a little recall (you miss neighbors that fell in an unprobed cluster) for far lower memory pressure and — critically — a read pattern dominated by scanning contiguous buckets rather than random graph hops.

Why the read pattern matters

Graph ANN (HNSW) traverses edges via random access, which is only fast when the whole graph is RAM-resident; spilling to disk turns it into random-read chains (concepts/sequential-vs-random-io). IVF's cluster-block layout means a query reads a handful of large contiguous blocks instead — a far better fit for storage-backed indexes, because sequential/block reads are cheap on SSD and object storage. This is precisely why IVF is the foundation Databricks chose for an object-storage-resident vector index.

Hierarchical IVF + quantization in lakebase_vector

Databricks' lakebase_vector builds on hierarchical IVF clustering: vectors are grouped into clusters stored as contiguous blocks; a query scores centroids in memory, then reads only the few promising blocks — "turning hundreds of random hops into a handful of large sequential reads." IVF composes with quantization: within a probed cluster, compact RaBitQ binary codes (concepts/quantization) shortlist candidates cheaply, then the bounded shortlist is reranked at full precision (patterns/cheap-approximator-with-expensive-fallback). Because index blocks are independent, a single query can also parallelize across CPU cores. (Source: sources/2026-09-28-databricks-lakebase-search)

Build parallelism is another IVF advantage: centroids are trained once on a small random sample (the only whole-dataset step), then every vector is independently assigned to its nearest centroid and written to its block — so the build fans across cores and can be offloaded to distributed engines.

Trade-offs vs graph ANN

IVF (cluster + scan) HNSW (graph)
Read pattern sequential block scans random graph hops
Memory centroids + working set whole graph must be RAM-resident
Storage-friendliness high (blocks on SSD/object store) low (spill → 10–50× slowdown)
Recall lever nprobe (clusters scanned) efSearch (nodes visited)
Build parallelism high (independent assignment) lower (graph insertion)

IVF is compared against graph ANN in concepts/vector-similarity-search, and sits alongside DiskANN (pure graph on SSD) and SPANN (partitioned posting lists + centroid graph on SSD) as the storage-resident ANN families.

Seen in

  • sources/2026-09-28-databricks-lakebase-search — hierarchical IVF clustering is the core of lakebase_vector's object-storage-resident index; centroid scoring in memory + contiguous block reads convert random hops into sequential reads.
Last updated · 766 distilled / 2,225 read