Современные ИИ-приложения — от семантического поиска до RAG-систем и рекомендаций — хранят смысл текстов и изображений в виде векторов-эмбеддингов. Типичный эмбеддинг от OpenAI или sentence-transformers содержит 768–1536 чисел. Найти среди миллионов таких векторов ближайший к запросу — задача нетривиальная, и классические алгоритмы с ней не справляются.
Причина — «проклятие размерности» (curse of dimensionality). С ростом числа измерений объём пространства увеличивается экспоненциально, данные становятся всё более разреженными, а расстояния между точками начинают «сливаться»: разница между ближайшим и самым далёким соседом стремится к нулю. Это явление называется concentration of distances. Алгоритм kd-tree, хорошо работающий в 2–3 измерениях, в высоких размерностях вынужден проверять почти все ветви дерева — то есть фактически превращается в полный перебор. Отсюда переход к приближённому поиску (Approximate Nearest Neighbor, ANN): вместо гарантированно точного ответа алгоритм с высокой вероятностью находит очень хороших кандидатов, пропуская заведомо неперспективные области пространства.
| Метрика | На что реагирует | Типичное применение |
|---|---|---|
| L2 (евклидово расстояние) | Направление и длина вектора | Поиск в пространстве с равномерным масштабом |
| Inner Product | Направление и длина (норма) | Рекомендательные системы, где длина несёт сигнал |
| Cosine Similarity | Только направление, длина игнорируется | Текстовые эмбеддинги, семантический поиск |
Прежде чем искать, нужно договориться о том, как измерять близость. Для эмбеддингов используют три основные метрики. L2 (евклидово расстояние) учитывает и направление, и длину вектора — два вектора, смотрящих в одну сторону, но разной длины, могут оказаться «далеко». Cosine Similarity смотрит только на угол между векторами и игнорирует длину — именно поэтому она стала стандартом для текстовых эмбеддингов. Inner Product чувствителен к норме: более «длинный» вектор получает преимущество даже при том же направлении, что полезно в рекомендательных системах, где длина вектора кодирует уверенность предсказания. Если нормализовать все векторы до единичной длины, Cosine Similarity и Inner Product становятся эквивалентны, а L2 монотонно связана с косинусом через длину хорды на единичной гиперсфере.
Алгоритм IVF (Inverted File Index) решает задачу поиска через кластеризацию. На этапе построения индекса всё множество векторов разбивается на k кластеров с помощью k-means: алгоритм итеративно выбирает центроиды, назначает каждую точку ближайшей из них и пересчитывает центры до сходимости. При поиске запрос сравнивается не со всеми векторами, а только с точками из нескольких ближайших кластеров — параметр nprobe задаёт, сколько кластеров просматривать. Чем больше nprobe, тем выше точность и тем медленнее поиск. IVF хорошо масштабируется и предсказуем, но качество кластеризации напрямую влияет на качество поиска: если граница между кластерами проходит рядом с запросом, часть релевантных векторов может оказаться в непросмотренном кластере.
HNSW (Hierarchical Navigable Small World) устроен принципиально иначе — это иерархический граф. Каждый вектор становится узлом, связанным рёбрами с несколькими ближайшими соседями. Граф строится в несколько слоёв: верхние слои разреженные и позволяют быстро «перепрыгивать» через пространство, нижние — плотные и обеспечивают точность. Поиск начинается на верхнем слое, жадно движется к ближайшему узлу и постепенно спускается вниз. Такая структура напоминает skip list, но в многомерном пространстве. HNSW, как правило, показывает более высокое качество поиска при той же скорости по сравнению с IVF, но требует больше памяти и сложнее в настройке.
Оба алгоритма реализованы в библиотеке FAISS от Meta, а также встроены в популярные векторные базы данных — Qdrant, Weaviate, Milvus, pgvector. Выбор между ними зависит от задачи: IVF предпочтителен при ограниченной памяти и большом числе векторов, HNSW — когда приоритет отдаётся точности и скорости запросов при достаточном объёме RAM.
