Faiss

Faiss — это библиотека для эффективного поиска похожих объектов и кластеризации плотных векторов. Она содержит алгоритмы, которые выполняют поиск в наборах векторов любого размера, вплоть до тех, которые могут не поместиться в оперативной памяти. В библиотеке также присутствует поддержка для оценки и настройки параметров. Faiss написана на C++ с полными обёртками для Python/numpy. Некоторые из самых полезных алгоритмов реализованы на GPU. Библиотека разработана Facebook AI Research.

НОВОСТИ

НОВОЕ: последний коммит (2018-02-22) поддерживает хранение перевёрнутых индексов на диске, см. demos/demo_ondisk_ivf.py

НОВОЕ: последний коммит (2018-01-09) включает реализацию метода индексации HNSW, см. benchs/bench_hnsw.py

НОВОЕ: теперь есть публичная группа обсуждения Facebook для пользователей Faiss по адресу https://www.facebook.com/groups/faissusers/

НОВОЕ: с 2017-07-30 лицензия на Faiss была смягчена до BSD с CC-BY-NC. Подробности см. в LICENSE.

ВведениеFaiss содержит несколько методов для поиска похожих объектов. Он предполагает, что экземпляры представлены в виде векторов и идентифицируются целыми числами, а векторы могут сравниваться с помощью расстояний L2 или скалярного произведения. Векторы, похожие на запросный вектор, — это те, которые имеют наименьшее расстояние L2 или наибольшее скалярное произведение с запросным вектором. Также поддерживается косинусное сходство, так как это скалярное произведение на нормированных векторах.Большинство методов, таких как те, основанные на двоичных векторах и компактных кодах квантизации, используют только сжатое представление векторов и не требуют хранения оригинальных векторов. Это обычно приносит меньшую точность поиска, но эти методы могут масштабироваться до миллиардов векторов в оперативной памяти на одном сервере.

Реализация на GPU может принимать входные данные из оперативной памяти CPU или GPU. На сервере с GPU индексы GPU могут использоваться как замена для индексов CPU (например, замените IndexFlatL2 на GpuIndexFlatL2) и копии в/из оперативной памяти GPU обрабатываются автоматически. Результаты будут быстрее, если оба входных и выходных данных остаются в оперативной памяти GPU. Поддерживается использование как одного, так и нескольких GPU.

Сборка

Библиотека реализована в основном на C++, с опциональной поддержкой GPU через CUDA и опциональным интерфейсом Python. Версия для CPU требует библиотеки BLAS. Она собирается с помощью Makefile и может быть упакована в образ Docker. Подробности см. в INSTALL.md.

Как работает FaissFaiss построен вокруг типа индекса, который хранит набор векторов и предоставляет функцию для поиска в них с использованием сравнения векторов по L2 и/или скалярному произведению. Некоторые типы индексов являются простыми базовыми линиями, такими как точный поиск. Большинство доступных структур индексации соответствуют различным компромиссам по отношению к- времени поиска

• качества поиска
• использованной памяти на каждый индексный вектор
• времени обучения
• необходимости внешних данных для несамоподобного обучения

Необязательная реализация на GPU предоставляет, вероятно (как на март 2017 года), самую быструю реализацию точного и приближенного (в сжатом домене) поиска ближайших соседей для высокоразмерных векторов, самую быструю реализацию алгоритма Ллойда для k-средних и самую быструю реализацию алгоритма выбора малого k. Реализация подробно описана здесь.

Полная документация Faiss

Вот основные точки входа для документации:

• полная документация, включая руководство, часто задаваемые вопросы и раздел диагностики доступна на странице wiki
• документация Doxygen содержит информацию по каждому классу
• для воспроизведения результатов из наших исследовательских статей Polysemous codes и Поиск схожести на миллиардах данных с использованием GPU, обратитесь к README для тестов производительности.

Авторы

Основные авторы Faiss:- Hervé Jégou инициировал проект Faiss и написал его первую реализацию

• Matthijs Douze реализовал большую часть Faiss для CPU
• Jeff Johnson реализовал все для Faiss на GPU## Ссылки

Ссылка для цитирования при использовании Faiss в исследовательской статье:

@article{JDH17,
  title={Поиск схожести на миллиардах данных с использованием GPU},
  author={Johnson, Jeff and Douze, Matthijs and J{\'e}gou, Herv{\'e}},
  journal={arXiv preprint arXiv:1702.08734},
  year={2017}
}

Присоединяйтесь к сообществу Faiss

Для публичного обсуждения Faiss или для вопросов есть публичная группа обсуждения Facebook по адресу https://www.facebook.com/groups/faissusers/. Мы отслеживаем страницу с проблемами репозитория. Вы можете сообщать о багах, задавать вопросы и т.д.

Лицензия

Faiss распространяется под лицензией BSD. Мы также предоставляем дополнительное патентное разрешение.