Vector Search Data Model

ai/ml
vector search
foundation
data model
Learn about the vector search data model in TileDB.

TileDB-Vector-Search implements different indexing algorithms that store the vector search data using different storage formats. Conceptually, TileDB-Vector-Search is storing and offering search functionalities for:

A user can perform the following types of queries:

The underlying data model used for indexing vectors in TileDB-Vector-Search depends heavily on the indexing algorithm used. However, TileDB uses certain high level structures across algorithms.

Cross-algorithm data model

All data and metadata required for a TileDB-Vector-Search index are stored inside a TileDB group (index_uri). All the listed, named arrays below are stored under this URI.

Updates

TileDB-Vector-Search offers support for updates for all different index algorithms by recording updates outside the main indexing storage structure and periodically consolidating them. This implementation is using the updates array, a sparse 1D array with dimension the external_id of the vectors and 1 variable length attribute encoding the vector itself or an empty value if the vector is deleted.

Object metadata

The object_metadata array is a 1D sparse array with external_id as dimension and attributes the user defined metadata attributes for their respective objects. This array stores metadata for each vector that can be used to implement similarity queries with structured filters.

Algorithm-specific storage format

TileDB-Vector-Search indexing algorithms implement different data models to support storing and querying vectors efficiently.

FLAT

FLAT is a straightforward implementation used to provide exact vector similarity search by computing the distance of the query vector and all the dataset vectors. It stores all the vectors in a non-ordered TileDB array.

Vectors

The shuffled_vectors array is a 2D dense array that contains all the vectors with no specific ordering. It stores the vectors as columns of the array and has dimensions:

  • rows - Corresponds to the vector dimensions (0, dimensions).
  • cols - Corresponds to the vector position in the set of vectors (0, size).

External IDs

The shuffled_ids array is a 1D dense array that maps vector positions in the vectors array to the external_id of each vector.

IVF_FLAT

IVF_FLAT is based on \(k\)-means clustering. Effectively, TileDB computes \(k\) separate clusters (as well as their centroids) of the dataset vectors, shuffling them in a way such that vectors in the same cluster appear adjacent on storage (to minimize I/O when retrieving those vectors).

Partition centroids

The partition_centroids array is a 2D dense array, storing the \(k\)-means centroids for the different vector partitions. It stores the centroid vectors as columns of the array and has dimensions:

  • rows - Corresponds to the vector dimensions (0, dimensions).
  • cols - Corresponds to the partition ID (0, partitions).

Partition indexes

The partition_indexes array is a 1D dense array recording the start index of each partition of vectors in the shuffled vectors array. This array has one dimension corresponding to the partition ID for which we record the start index. The end index of each partition corresponds to the start index of the next partition.

Shuffled vectors

The shuffled_vectors array is a 2D dense array that contains all the dataset vectors shuffled based on their partition. Each vector partition is stored in a consecutive index range of this array. The vectors are stored as columns of the array which has dimensions:

  • rows - Corresponds to the vector dimensions (0, dimensions).
  • cols - Corresponds to the vector position in the set of vectors (0, size).

Shuffled IDs

The shuffled_ids array is a 1D dense array that maps vector indices in the shuffled vectors array to the external_id of each vector.

Vamana

VAMANA is a graph-based algorithm based on Microsoft’s DiskANN vector search library (Subramanya, Suhas Jayaram et al. “DiskANN : Fast Accurate Billion-point Nearest Neighbor Search on a Single Node.” NeurIPS (2019).). It stores all of the vectors in a non-ordered TileDB array, as well as a graph that is used for faster searching.

Vectors

The shuffled_vectors array is a 2D dense array that contains all the vectors with no specific ordering. It stores the vectors as columns of the array and has dimensions:

  • rows - Corresponds to the vector dimensions (0, dimensions).
  • cols - Corresponds to the vector position in the set of vectors (0, size).

External IDs

The shuffled_ids array is a 1D dense array that maps vector positions in the vectors array to the external_id of each vector.

Adjacency row indices

The adjacency_row_index_array_name is a 1D dense array that holds the edges for each node in the graph. Each value indicates where the neighbors (edges) for each successive node start in Adjacency IDs and Adjacency Scores. For example, you might have [0, 2, 8, 13], which indicates that the neighbors for node 0 start at index 0, the neighbors for node 1 start at index 2, and the neighbors for node 2 start at index 8. The final value is the end of the array, so the neighbors for node 2 end at index 13. With that information, you can look in Adjacency IDs to determine the destination node. The source node can be inferred by the index of the Adjacency Row Indices array. Once you know the source or destination node index, you can look at that index in Vectors or External IDs to get the vector or external ID for that node.

Adjacency IDs

The adjacency_ids array is a 1D dense array that holds the neighbors of the graph. Each value is an index into the Vectors and External IDs arrays. This only holds the destination nodes of the graph. The source node is in the Adjacency Row Indices array, which itself points to Adjacency IDs.

Adjacency scores

The adjacency_scores is a 1D dense array that follows the same pattern as Adjacency IDs, but holds the edge distance instead of the destination node.