Привет, друзья!
Во многих задачах - от классификации и кластеризации до поиска похожих объектов и генерации рекомендаций - важно уметь эффективно находить ближайшие векторы в высокоразмерном пространстве. Но как только число векторов превышает несколько тысяч, простые методы из sklearn и numpy начинают работать непозволительно медленно🐌 При масштабах же в миллионы объектов стоит задуматься уже не только про быстроту, но и про оптимизацию, балансируя между точностью, скоростью и потреблением памяти.

В таких случаях приходят на помощь библиотеки для быстрого KNN в высокоразмерных пространствах. Самая известная, пожалуй, Faiss от Facebook AI Research. Вот её главные преимущества:

🔠 Подкапотная реализация на C++ с SIMD-оптимизациями и продуманным управлением памятью в Python-обёртке. А ещё это значит, что Faiss не блокируется GIL'ом и отлично масштабируется по потокам: можно параллелить поиск через joblib.Parallel или ThreadPoolExecutor.
🔠 Поддержка GPU, что также даёт прирост скорости в десятки раз.
🔠 Гибкость индексов: от точного поиска (Flat) до приближённых структур с квантованием и кластеризацией.

Рассмотрим основные типы индексов:

🔠 IndexFlat - базовая реализация, которая хранит все векторы в RAM и выполняет точный линейный поиск. Работает быстро на малых объемах (<100K векторов), также идеален для отладки или в случаях, если поиск каждый раз нужно осуществлять в разных ограниченных подпространствах векторов (тогда просто запускаете с тем же Parallel:)).
🔠 IndexIVF (Inverted File Index) - предварительно перед поиском он кластеризует всё пространство векторов (например, с помощью k-means).
При поиске сначала выбираются N ближайших кластеров, а затем производится поиск заданной глубины K внутри них.
На моей практике, даже с учётом времени на обучение индекса, IVF ускорил процесс поиска в ~8 раз по сравнению с Flat+Parallel, при этом точность результата по метрикам проявилась только в 5-м знаке после запятой (ещё и в бОльшую сторону! 😎)
Но есть уже озвученное "НО" - такой индекс требует предварительного обучения, и на это нужно время. Поэтому имеет смысл его использовать, если запросы каждый раз делаются из одинакового и фиксированного пространства.
Если захотите воспользоваться IVF, то упомянутые N и K лучше брать как √d и 2–4*(размер топа, который вы ищете) соответственно, где d - количество векторов в базе для поиска.
🔠 IndexIVFPQ (Product Quantization) добавляет к IVF еще одно ускорение - сжимает векторы до компактного кода (например, 8 байт вместо 128 float32). Работает ещё быстрее и экономит память при минимуме потерь в точности. Имеет смысл посмотреть в сторону этого подхода, если у вас порядка миллиарда векторов.
🔠HNSW-семейство индексов (Hierarchical Navigable Small World) - индексы на основе графов малого мира, где каждый вектор представляется как вершина, связанная с соседями в многослойной структуре. Поиск происходит за счёт навигации по графу: сначала на грубом уровне, затем всё точнее.
Такие индексы не требуют предварительного обучения и хорошо подходят для динамических баз, где данные часто добавляются на лету. Отличаются высокой точностью даже при небольшой глубине поиска, но потребляют больше памяти и не поддерживаются на GPU.

Полезные ссылки:
🔠 Официальный репозиторий Faiss.
Там же ссылка на quick start и базу jupyter-ноутбуков с примерами кода на Python
🔠 Ещё пара хороших туториалов с примерами кода тут и тут
⚠️Если решите установить версию с поддержкой GPU, лучше использовать эту

Лёгкой и солнечной недели! ☀️

#mlops@data_easy