Indexes

Indexes accelerate similarity search over high-dimensional vectors. Depending on the configuration, indexing can be managed automatically or controlled manually (for example, create and manage indexing around bulk loads).

Vector indexing is what makes vector search fast at scale. Oracle VecDB supports the following approximate nearest neighbor index types:

Vector indexes are a class of specialized indexing data structures that are designed to accelerate similarity searches using high-dimensional vectors. They use techniques such as clustering, partitioning, and neighbor graphs to group vectors representing similar items, which drastically reduces the search space, thereby making the search process extremely efficient. Create vector indexes on your vector embeddings to use these indexes for running similarity searches over huge vector spaces.

Oracle AI Database supports the creation of two different types of indexes.

Hierarchical Navigable Small World (HNSW)

HNSW indexing is a graph-based Approximate Nearest Neighbor (ANN) algorithm for very fast, scalable similarity searches on large vector data sets. HNSW graphs are structured using principles from small world networks along with layered hierarchical organization.

HNSW indexes are best for read-heavy semantic search and for instances when the dataset does not frequently change.

The idea of Navigable Small World (NSW) is to build a proximity graph in which each vector connects to several others based on the following characteristics:

When the combination of the listed thresholds is too high, you can end up with a densely connected graph, which can slow down the search process. If the combination of thresholds is too low, the graph can become too sparse, or disconnected, which can make it challenging to find a path between certain vectors during the search.

As the graph is traversed, dynamically updated lists of candidates, vectors encountered during the traversal, and results, vectors closest to the query vector found thus far, are maintained. The search process concludes once there are no vectors in the candidates list closer than the farthest in the results list, indicating that a local minimum has been reached and the closest vectors to the query vector have been identified.

The hierarchical element of HNSW indexes enhances the NSW model by introducing a multilayer hierarchy, which is implemented by distributing the graph’s connections across several layers. Each subsequent layer contains a subset of the vectors from the layer below. This ensures that the top layers capture long-distance links, while lower layers focus on shorter links, facilitating fine-grained, local navigation. As a result, searches begin at higher layers to quickly approximate the region of the target vector, then move to lower layers for a more precise search. This significantly improves the search efficiency and accuracy by leveraging shorter links (smaller distances) between vectors as one moves from the top layer to the bottom.

For more information about HNSW indexes, see In-Memory Neighbor Graph Vector Index in Oracle AI Database AI Vector Search User’s Guide.

Inverted Flat File (IVF)

IVF indexing is a method for approximate nearest neighbor (ANN) search, implemented by partitioning vector space, thus narrowing the search area, for efficient querying. IVF indexes allow you to balance high-search quality with reasonable speed.

IVF indexes are ideal for when you are dealing with large or changing collections, and tunable search cost is an important consideration.

Partitions, or clusters, are used to divide the vector space into sections. Data points are added to identify centroids, each one representing the average vector (center of gravity) of the corresponding partition. The number of centroids (k) is determined by the size of the dataset (n). Typically, k is set to the square root of n, though it can be adjusted using the NEIGHBOR PARTITIONS parameter during index creation. The centroids are calculated by a training pass over the vectors, with a goal of minimizing the total distance of each vector from the closest centroid.

When a query vector is provided, the search algorithm identifies the nearest i centroids, where i defaults to the square root of k, but can be adjusted for a particular query by specifying the NEIGHBOR PARTITION PROBES parameter. This adjustment allows for a trade-off between search speed and accuracy. Higher values for this parameter will result in higher accuracy.

Once the i partitions are determined, they are scanned to identify the nearest vectors. This method constitutes an approximate search as it limits the search to a subset of partitions, accelerating the process but potentially missing closer vectors in unexamined partitions. A target accuracy can optionally be specified as a percentage value to influence the number of partitions used to probe the search. A higher value will result in higher accuracy.

For more information about IVF indexes, see Neighbor Partition Vector Index in Oracle AI Database AI Vector Search User’s Guide.

Parent topic: How Oracle VecDB Works