ScaNN – алгоритм Google, основанный на поиске по сходству векторов. В основе его лежит преобразование входных данных в многомерные векторы, эмбеддинги, благодаря которым для пользовательского запроса можно найти наиболее близкие эмбеддинги в базе данных.
Алгоритм ScaNN использует методы сжатия векторов из набора данных для ускорения вычислений расстояний между векторами. Собственно, сам ScaNN и представляет собой высокопроизводительную библиотеку поиска по сходству векторов, значительно превосходящую по производительности другие аналогичные библиотеки поиска.
Поиск на базе эмбеддингов эффективен при ответе на запросы, основанные на понимании семантики, смысла запроса, в отличие от обычного цитатного поиска, основанного на ключевых словах. Запросы и элементы базы данных отображаются в общем векторном пространства, в котором похожие элементы находятся рядом. Для выбора наиболее релевантных данных алгоритм сопоставляет запрос с другими элементами пространства эмбеддингов.
Размеры базы данных могут исчисляться миллионами и миллиардами элементов, что сказывается на производительности поисковой системы. Следствием этого становится меньшая точность результатов поиска в сравнении с поиском, основанным на методе перебора.
Сжатие элементов базы данных выполняется с помощью квантования. Предыдущие схемы векторного квантования минимизировали расстояние между каждым вектором и его квантованной формой. ScaNN использует анизотропное квантование, позволяющее получить более точный результат с большей производительностью.