Привет, друзья!
Во многих задачах - от классификации и кластеризации до поиска похожих объектов и генерации рекомендаций - важно уметь эффективно находить ближайшие векторы в высокоразмерном пространстве. Но как только число векторов превышает несколько тысяч, простые методы из 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

Привет, друзья!
Держите небольшую, но максимально эффективную подборку ресурсов для подготовки к собеседованиям по Data Science: практические задачи с ML-спецификой, вопросы от FAANG и полезные чек-листы👇

🔠 StrataScratch
Платформа с практическими задачами на SQL, Pandas, Polars и PySpark. Вопросы собраны из интервью реальных компаний (Amazon, Google, Lyft и др.). Можно фильтровать по уровню сложности и компании, а код исполняется прямо в браузере. Задачи есть как на выборку данных, так и на аналитическое мышление, манипуляции с датами, оконные функции и многое-многое другое!

🔠 DataLemur
Этот сайт для отработки чисто SQL-навыков. Все задачи делятся по темам (JOIN, агрегаты, оконные функции...), по сложности и по компаниям. Встроенный SQL-редактор позволяет сразу проверять решение. Есть подсказки, подробные разборы, статистика по сложности и рейтинг задач. И в отличие от sql-ex.ru с гораздо более современным интерфейсом и интересными задачами😁

🔠 Extremesarova/ds_resources (github)
Большой список ресурсов по всем темам для подготовки: Python, статистика, машинное обучение, SQL, A/B‑тесты, product sense, system design. Есть ссылки на видео, статьи, тренажёры и шаблоны. Удобно использовать как базу знаний или дорожную карту перед собеседованием.

🔠 alexeygrigorev/data-science-interviews (github)
Ещё один полезный чек-лист: краткая и чёткая структура по темам, которые часто встречаются на интервью. Плюс есть ссылки на полезные книги, туториалы и примеры вопросов. Особенно приятно, что есть разделы про системный дизайн и поведенческие интервью именно для DS.

А какие ресурсы нравятся вам? Может, есть любимые тренажёры или подборки, которые прокачали вас перед интервью? Поделитесь в комментариях😊

Успешной подготовки и уверенности на собесах! 💪

#карьера@data_easy