Какие библиотеки использовать для поиска ближайших соседей

Что проверяют

Понимаете ли вы разницу между точным и приближённым поиском и умеете ли выбрать инструмент под объём данных. Почти всегда следом спрашивают, как вы проверяете, что приближённый индекс не теряет нужных соседей.

Как отвечать

Разделите инструменты по масштабу:

• scikit-learn: NearestNeighbors и KNeighborsClassifier дают точный поиск. Параметр algorithm выбирает kd_tree, ball_tree или brute, по умолчанию auto. Деревья хороши на малой размерности, а на сотнях измерений выигрыша почти нет и поиск сводится к перебору;
• faiss: точные IndexFlatL2 и IndexFlatIP, приближённые IndexIVFFlat (требует обучения, скорость и точность регулирует nprobe), IndexIVFPQ со сжатием векторов и IndexHNSWFlat. Есть сборка под GPU;
• hnswlib: компактная реализация графа HNSW, параметры M и ef_construction при построении, ef при запросе;
• Annoy: лес случайных проекций, индекс сохраняется в файл и открывается через mmap несколькими процессами. После build добавлять элементы нельзя, только пересобирать;
• pynndescent и ScaNN: ещё два варианта ANN, первый работает внутри UMAP;
• векторные базы: Qdrant, Milvus или pgvector, если нужны фильтры, обновления и хранение, а не только индекс в памяти.

Выбор объясняйте цифрами. Миллион векторов размерности 768 во float32 занимает около 3 ГБ, точный перебор такого объёма на каждый запрос уже медленный, поэтому берут ANN. Качество меряют как recall@k относительно точного поиска на выборке запросов и строят кривую recall против запросов в секунду, как в ann-benchmarks.

Где спотыкаются

Путают метрики. Для косинусной близости в FAISS векторы нормируют и используют IndexFlatIP, иначе скалярное произведение даёт не то, что ожидали.

Не масштабируют признаки перед kNN на табличных данных. Признак в рублях задавит признак в долях, и соседи определятся одной колонкой.

Считают приближённый поиск бесплатным. Без замера recall на своих данных нельзя сказать, сколько релевантных соседей теряется при выбранных nprobe или ef.