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 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.

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

• HNSW indexes are well suited for workloads that require high query throughput and low search latency. They support read scalability as query demand grows. Because HNSW maintains a graph-based index in memory, memory consumption can be higher for large datasets. Scalar quantization can reduce the memory footprint while retaining HNSW performance.
• IVF indexes provide a memory-efficient option for very large datasets and can scale to indexes containing billions of vectors. Their partition-based structure enables large-scale similarity search with a lower memory footprint.

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.

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:

• The distance between vectors.
• The maximum number of closest vector candidates considered at each step of the search during insertion, specified using the EFCONSTRUCTION parameter.
• The maximum number of connections permitted per vector, specified using the NEIGHBORS parameter.

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.

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.

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