Зачем нужен приближённый поиск
В основе современных рекомендательных систем и семантического поиска лежат векторные эмбеддинги: каждый товар и каждый пользователь представлены точкой в многомерном пространстве. Задача — найти ближайшие точки к запросу.
Точный поиск (перебор всех векторов) слишком медленен при больших каталогах:
Каталог: 5 000 000 товаров
Размерность эмбеддинга: 128
Точный поиск: ~640 млн операций на запрос → 500–2000 мс
ANN (HNSW): <5 мс при recall > 95%
ANN решает эту задачу, строя индексные структуры, позволяющие отсечь большинство нерелевантных векторов без их проверки.
Основные алгоритмы
| Алгоритм | Принцип | Сильная сторона |
|---|---|---|
| HNSW | Иерархический граф | Высокая точность, динамическое добавление |
| IVF (Inverted File) | Кластеризация + поиск в кластерах | Экономия памяти на больших датасетах |
| LSH | Хеширование по случайным проекциям | Простота, работает без GPU |
| ScaNN (Google) | Анизотропная квантизация | Высокая скорость, подходит для Search |
FAISS (Meta) — самая распространённая библиотека, поддерживает несколько алгоритмов и GPU-ускорение.
Применение в e-commerce
Похожие товары. Для страницы карточки товара нужно за миллисекунды найти 10–20 визуально или семантически похожих. ANN-индекс по товарным эмбеддингам решает это в реальном времени.
Семантический поиск. Запрос «тёплое пальто для осени» → эмбеддинг запроса → ANN-поиск по векторам товаров → релевантные результаты без точного совпадения слов.
Персонализированные рекомендации. Two-tower модель производит вектор пользователя и векторы товаров. ANN-поиск находит товары, ближайшие к вектору пользователя, за O(log n) вместо O(n).
Компромисс: точность vs скорость
ANN настраивается через параметры индекса. Например, в HNSW ключевые параметры:
— ef_construction — точность при построении индекса (влияет на время индексирования)
— ef_search — точность при поиске (влияет на латентность)
Повышение этих параметров улучшает recall, но замедляет поиск. В продакшне подбирается баланс: обычно ef_search настраивают так, чтобы recall@10 ≥ 95% при латентности < 10 мс.
Важно: при обновлении каталога (добавление новых SKU) HNSW позволяет добавлять векторы инкрементально. IVF-индексы часто требуют полной перестройки — важно учитывать при выборе архитектуры для каталогов с частыми обновлениями.