Vector search
Concept of vector search
Vector search, also known as nearest neighbor search (NN), is an optimization problem where the goal is to find the nearest vector (or a set of vectors) in a given dataset relative to a specified query vector. The proximity between vectors is determined using distance or similarity metrics.
Vector search is actively used in the following areas:
- recommendation systems
- semantic search
- search for similar images
- anomaly detection
- classification systems
In addition, vector search in YDB is widely applied in machine learning (ML) and artificial intelligence (AI) tasks. It is particularly useful in Retrieval-Augmented Generation (RAG) approaches, which utilize vector search to retrieve relevant information from large volumes of data, significantly enhancing the quality of generative models.
Methods for solving vector search tasks can be divided into three major categories:
The choice of a method depends on the number of vectors and the nature of the workload. Exact methods search slowly but update quickly, whereas indexes do the opposite.
Exact vector search
The foundation of the exact method is the calculation of the distance from the query vector to all the vectors in the dataset. This algorithm, also known as the naive approach or brute force method, has a runtime of O(dn), where n is the number of vectors in the dataset, and d is their dimensionality.
Exact vector search is best utilized if the complete enumeration of the vectors occurs within acceptable time limits. This includes cases where they can be pre-filtered based on some condition, such as a user identifier. In such instances, the exact method may perform faster than the current implementation of vector indexes.
Main advantages:
- No need for additional data structures, such as specialized vector indexes.
- Full support for transactions, including in strict consistency mode.
- Instant execution of data modification operations: insertion, update, deletion.
Learn more about exact vector search.
Approximate vector search without index
Approximate methods do not perform a complete enumeration of the initial data. This allows significantly speeding up the search process, although it might lead to some reduction in the quality of the results.
Scalar Quantization is a method of reducing vector dimensionality, where a set of coordinates is mapped into a space of smaller dimensions.
YDB supports vector searching for vector types Float, Int8, Uint8, and Bit. Consequently, it is possible to apply scalar quantization to transform data from Float to any of these types.
Scalar quantization reduces the time required for reading and writing data by decreasing the number of bytes. For example, when quantizing from Float to Bit, each vector is reduced by 32 times.
Approximate vector search without an index uses a very simple additional data structure - a set of vectors with other quantization. This allows the use of a simple search algorithm: first, a rough preliminary search is performed on the compressed vectors, followed by refining the results on the original vectors.
Main advantages:
- Full support for transactions, including in strict consistency mode.
- Instant application of data modification operations: insertion, update, deletion.
Learn more about approximate vector search without index.
Approximate vector search with index
When the data volume significantly increases, non-index approaches cease to work within acceptable time limits. In such cases, additional data structures are necessary such as vector indexes, which accelerate the search process.
Main advantage:
- ability to work with a large number of vectors
Disadvantages:
- index construction may take considerable time
- in the current version, data modification operations such as insertion, update, and deletion are not supported