This topic describes the vector models supported by OpenSearch Vector Search Edition.
Introduction to vector retrieval
In the current information age, information has expanded beyond text to include multimodal information such as images, videos, and audio. Multimodal information can convey information that text cannot express, such as colors, shapes, motion dynamics, sounds, and spatial relationships.
At the same time, the modalities of information in various fields have also changed significantly:
In such multimodal scenarios, information is divided into two major categories (structured and unstructured):
Unstructured data is often difficult for computers to understand, and traditional text tokenization-based retrieval can no longer meet the search requirements of various fields. Vectors solve this problem perfectly.
So what is a vector, and how is retrieval performed by using vectors?
Unstructured data generated in the physical world is converted into structured multi-dimensional vectors, and these vectors are used to represent entities and the relationships between entities.
Then, the distances between vectors are calculated. Typically, a shorter distance indicates higher similarity. The top results with the highest similarity are retrieved to complete the retrieval.
Vector retrieval algorithms
linear
The linear algorithm performs linear calculations on all vector data.
Scenarios: 100% recall rate
Disadvantages: Low efficiency for large data volumes and high resource (CPU and memory) consumption
Clustering algorithms
Quantized Clustering
Introduction:
Quantized Clustering (QC) is a vector retrieval algorithm developed by Alibaba based on k-means clustering. First, the vector documents are clustered into n centroids, and each document is assigned to its nearest centroid, which builds n inverted lists. The n centroids and their corresponding inverted lists make up the main content of a QC index. During retrieval, the distances between the query and some of the centroids are calculated, and the centroids with the shortest distances are selected. Then, the distances between the query and the documents in the inverted lists of these centroids are calculated, and the top k documents with the shortest distances are returned.
In particular, QC supports fp16/int8 numeric quantization, which can reduce the index size and improve retrieval performance. However, it may degrade the recall effect. You can determine whether to configure quantization based on your business requirements.
The QC algorithm is suitable for real-time data scenarios, or scenarios in which GPU resources are available and low latency is required.
Parameter tuning:
Performance comparison:
HNSW (Hierarchical Navigable Small World)
Introduction:
Hierarchical Navigable Small World (HNSW) is a vector retrieval algorithm based on proximity graphs. First, a proximity graph is built, in which edges are created between vectors that are close to each other. The vectors and their neighbor information make up the main content of an HNSW index. During retrieval, traversal starts from the entry node. The distances between the query and all neighbors of the entry node are calculated, and the nearest neighbor is selected as the next node to traverse. This process iterates until it converges and the retrieval stops. Convergence means that none of the neighbors of the current node is closer to the query than the nearest node already retrieved.
To accelerate convergence, HNSW borrows the query logic of skip lists and builds a multi-layer proximity graph structure. Retrieval is performed from top to bottom. The retrieval logic of each layer is roughly the same (the logic of layer 0 differs slightly). After the traversal on layer k converges to a node, the node is used as the entry node of layer k-1, and the traversal continues on layer k-1. Compared with layer k-1, layer k contains sparser nodes with longer distances between them. This allows larger steps and faster iteration when traversing layer k.
Parameter tuning:
QGraph algorithm
Introduction:
Quantized Graph (QGraph) is an improved algorithm based on HNSW developed in-house by OpenSearch. During index building, the raw data of users is automatically quantized and then built into a graph index. Compared with the HNSW algorithm, the QGraph algorithm can effectively reduce the index size and memory overhead. The index can be reduced to as little as 1/8 of its original size. In addition, thanks to CPU instruction optimizations for integer calculations, the performance of QGraph is several times higher than that of HNSW. Because quantization reduces the distinguishability of vectors, the recall rate of QGraph is lower than that of HNSW. In real-world scenarios, you can mitigate this impact by retrieving more results.
QGraph supports int4, int8, and int16 quantization. Different quantization levels have different impacts on the memory usage of vector indexes, query performance, and recall rate. In general, the fewer the integer bits, the smaller the memory usage of vector indexes, the higher the performance, and the lower the recall rate. Due to the underlying CPU instruction sets, the performance and recall rate of int16 quantization are almost the same as those without quantization.
Parameter tuning:
CAGRA algorithm
Introduction:
CUDA ANN GRAph-based (CAGRA) is a vector retrieval algorithm based on proximity graphs. It is optimized for NVIDIA GPUs and is suitable for scenarios with high concurrency and batch requests.
Unlike the HNSW algorithm, the proximity graph built by the CAGRA algorithm has only one layer for the purpose of parallel computing. During a query, the algorithm maintains an ordered candidate set while iterating. In each iteration, the best top K nodes in the candidate set are selected as search starting points, and their neighbors are used to try to update the candidate set. This process iterates until all the top K nodes in the candidate set have been used as search starting points, at which point the algorithm is considered to have converged.
The CAGRA algorithm is implemented with two strategies: single-CTA and multi-CTA. Single-CTA maps the query of a single vector to a single thread block for execution, which is more efficient when the batch size is large. Multi-CTA uses multiple thread blocks to execute the query of a single vector. When the batch size is small, multi-CTA can make better use of the parallel computing capabilities of GPUs and achieves a higher recall rate. However, when the batch size is large, its throughput is lower than that of the single-CTA strategy. During actual calls, the optimal algorithm is automatically selected based on the workload.
Parameter tuning:
DiskANN algorithm
Introduction:
DiskANN is a disk-based approximate nearest neighbor search technology designed for processing ultra-large datasets. It uses the Vamana graph algorithm to efficiently store data on disks with limited memory while maintaining efficient vector indexing and retrieval.
The DiskANN algorithm is supported only when the instance family of data nodes is SSD.
Parameter tuning:
CagraHnsw algorithm
Introduction:
CagraHnsw is a vector retrieval algorithm developed in-house by OpenSearch. It combines the advantages of the CAGRA and HNSW algorithms and is suitable for scenarios in which massive amounts of data must be built quickly.
In the index building phase, the CagraHnsw algorithm is similar to the CAGRA algorithm and uses GPUs to build indexes. The index files are converted into a format that can be used by the HNSW algorithm, and the HNSW algorithm on CPUs is used for searches in the retrieval phase. This strategy leverages the advantage of the CAGRA algorithm in efficient GPU-based building, without requiring users to use more expensive GPU instance types in the retrieval phase. Compared with the CAGRA algorithm, it is more cost-effective when there are no sustained high-concurrency queries.
Vector distance types
Vector retrieval calculates the similarity between vectors and returns the top K vectors with higher similarity. In this process, the similarity between vectors is obtained by calculating distances. Typically, a smaller score indicates a shorter distance between vectors, and a larger score indicates a longer distance.
Different vector spaces define different distance metrics to calculate the distances between vectors. OpenSearch Vector Search Edition supports the following metrics: Euclidean metric, inner product metric, and cosine distance.
Euclidean distance (SquareEuclidean)
Euclidean distance is the straight-line distance between two vectors. As one of the most commonly used distance metrics, Euclidean distance can be obtained by calculating the square root of the sum of the squared coordinate differences between two vectors. A smaller Euclidean distance indicates that two vectors are more similar. The Euclidean distance is calculated by using the following formula:
Inner product distance (InnerProduct)
The inner product is the dot product or scalar product of two vectors. A larger inner product indicates higher similarity. It is obtained by multiplying the elements at corresponding positions of the two vectors and summing the products. The inner product metric is commonly used in search and recommendation scenarios. Generally, whether to use the inner product metric depends on whether the algorithm uses an inner product model. The inner product is calculated by using the following formula:
Cosine distance
Cosine distance is the cosine of the angle between two vectors. Valid values: [-1, 1]. A value of -1 indicates that the two vectors point in opposite directions and have the lowest similarity. A value of 1 indicates that the two vectors point in the same direction and have the highest similarity. A value of 0 indicates that the two vectors are perpendicular. The closer the value is to 1, the more similar the vectors are. Cosine distance is commonly used in text similarity retrieval scenarios. It is calculated by using the following formula:
