Quake Index Architecture

Overview

The Quake Index is an adaptive, hierarchical indexing system for vector search. It uses a partitioned index design in which the dataset is recursively clustered into a multi-level structure. The QuakeIndex class coordinates index construction, query processing, and maintenance. Underneath, a DynamicInvertedLists object stores multiple IndexPartition instances, each representing a subset of vectors. A PartitionManager controls how vectors are assigned to partitions, while a QueryCoordinator manages query execution. Finally, a MaintenancePolicy adapts the index to evolving data and query patterns over time.

QuakeIndex Class Components

The diagram below illustrates the main components of the QuakeIndex class and the primary operations each is responsible for:

• PartitionManager: Handles modifications of vectors and partitions. Responsible for add() and remove()

• QueryCoordinator: Manages search operations. Used in search() and add().

• CentroidIndex: A QuakeIndex over the centroids for efficient searching of centroids.

• MaintenancePolicy: Maintains partition access counts and oversees periodic index maintenance.

Detailed Components

• Query Coordinator
  • Overview
  • Coordinator Architecture Diagram
  • Key Components
  • Workflow and Job Distribution
• MaintenancePolicy
  • Overview
  • Key Methods
  • Configuration and Parameters
• PartitionManager
  • Overview
  • Key Responsibilities
  • Differences from DynamicInvertedLists
  • Usage
• DynamicInvertedLists
  • Overview
  • Key Responsibilities
  • Limitations
• IndexPartition
  • Overview
  • Key Responsibilities
  • Public Interface
  • Usage Considerations
  • IndexPartition Layout
  • Conclusion

Data Layout

The index is organized hierarchically. Each level uses centroids to summarize the partitions of the next level. Every centroid corresponds to a cluster that can be recursively subdivided. At the base level, partitions store the actual encoded vectors and their IDs. The figure below shows a toy 3-level Quake Index with three partitions per level and 27 base vectors. Although this example uses uniform partition sizes, real-world sizes vary based on data distribution.

Example with 3 levels and 3 partitions per level and 27 base vectors.

Query Processing Example

When a query is issued, it descends the index hierarchy from the top level to the base level where vectors are stored. At each level, the query vector is compared against centroids to determine which partitions to scan next. This continues until the base level is reached, where the actual vectors are compared with the query. The figure below illustrates a 3-level Quake Index example. Scanned partitions are shown in full color, while non-scanned partitions are faded.

Query Processing Example (3-Level Quake Index)

Index Memory Layout

The following figure demonstrates how the index can be distributed across three NUMA nodes, each with three CPUs. Partitions in each NUMA node’s memory region are pinned to specific CPUs, enabling efficient local access. Level-2 partitions are shown in green, Level-1 in blue, and Level-0 in purple. In order to distribute the top-level, the single top-level partition is sharded across NUMA nodes.

Hardware Layout: Index Distributed Across 3 NUMA Nodes (each with 3 CPUs)