Векторный поиск
Понятие векторного поиска
Векторный поиск, также известный как поиск ближайшего соседа (NN), представляет собой задачу оптимизации, в которой необходимо найти ближайший вектор (или множество векторов) в данном наборе данных относительно заданного вектора запроса. Близость между векторами определяется с помощью метрик расстояния или сходства.
Одним из распространённых подходов, особенно при работе с большими наборами данных, является приближённый поиск ближайших соседей (ANN search), который позволяет получать более быстрые результаты за счёт возможной потери точности.
Векторный поиск активно используется в следующих областях:
- рекомендательные системы;
- семантический поиск;
- поиск похожих изображений;
- обнаружение аномалий;
- классификационные системы.
Кроме того, векторный поиск в YDB широко применяется в задачах машинного обучения (ML) и искусственного интеллекта (AI). Он особенно полезен в подходах Retrieval-Augmented Generation (RAG), которые используют векторный поиск для извлечения релевантной информации из больших объемов данных, что значительно улучшает качество генеративных моделей.
Методы решения задач векторного поиска можно разделить на три крупных категории:
Выбор метода зависит от числа векторов и от характера нагрузки. Точные методы медленно ищут и быстро обновляются, индексы - наоборот.
Точный векторный поиск
В основе точного метода лежит вычисление расстояния от вектора запроса до всех векторов в наборе данных. Этот алгоритм, также известный как наивный подход или метод грубой силы, имеет время выполнения O(dn), где n — количество векторов в наборе данных, а d — их размерность.
Точный векторный поиск лучше использовать, если полный перебор искомых векторов происходит за приемлемое время. В том числе, когда их можно предварительно отфильтровать по некоторому условию, например, по идентификатору пользователя. В таких случаях точный метод может работать быстрее, чем текущая реализация векторных индексов.
Основные преимущества:
- отсутствие необходимости в дополнительных структурах данных, таких как специализированные векторные индексы;
- полная поддержка транзакций, в том числе в режиме строгой согласованности;
- мгновенное применение операций модификации данных: вставка, обновление, удаление.
Подробнее о точном векторном поиске.
Приближенный векторный поиск без индекса
Приближенные методы не осуществляют полный перебор исходных данных. Это позволяет значительно ускорить процесс поиска, хотя и может привести к некоторому снижению качества результатов.
Скалярное квантование — это метод уменьшения размерности векторов, при котором множество координат отображается в пространство меньшей размерности.
YDB поддерживает векторный поиск по векторам типов Float, Int8, Uint8, Bit. Следовательно, возможно применение скалярного квантования для преобразования данных из Float в любой из этих типов.
Скалярное квантование сокращает время, необходимое для чтения и записи данных, за счёт уменьшения числа байт. Например, при квантовании из Float в Bit каждый вектор сокращается в 32 раза.
Приближенный векторный поиск без индекса использует очень простую дополнительную структуру данных - множество векторов с другими квантованием. Это позволяет использовать простой алгоритм поиска: сначала грубый предварительный поиск по сжатым векторам, а затем уточнять результаты по исходным векторам.
Основные преимущества:
- полная поддержка транзакций, в том числе в режиме строгой согласованности;
- мгновенное применение операций модификации данных: вставка, обновление, удаление.
Подробнее о приближенном векторном поиске без индекса.
Приближенный векторный поиск с индексом
Когда объем данных существенно увеличивается, подходы без индекса перестают работать за приемлемое время.
В таких случаях необходимы дополнительные структуры данных — векторные индексы, которые ускоряют процесс поиска.
Основное преимущество:
- возможность работы с большим числом векторов.
Недостатки:
- построение индекса может занимать существенное время;
- в текущей версии не поддерживаются операции модификации данных: вставка, обновление, удаление.