Компания Microsoft опубликовала исходные тексты библиотеки машинного обучения SPTAG (Space Partition Tree And Graph) с реализацией алгоритма приблизительного поиска ближайшего соседа.
Ключевое отличие векторного поиска от поиска по ключевым словам заключается в том, что векторы учитывают смысл и сходство данных, а не только символьные совпадения. Векторы формируются на основе модели машинного обучения, которая учитывает также сопутствующую статистику, уточняющую связи и позволяющую более точно оценить суть запроса (например, учитываются связь запроса с последующими переходами в поисковой выдаче). Несмотря на то, что идеи применения векторных хранилищ в поисковых системах витают уже достаточно давно, на практике их внедрению мешает большая ресурсоёмкость операций с векторами и ограничения в масштабируемости.
Совмещение методов глубинного машинного обучения с алгоритмами приблизительного поиска ближайшего соседа позволило довести производительность и масштабируемость векторных систем до уровня, приемлемого для крупных поисковых систем. Например, в Bing для векторного индекса размером более 150 миллиардов векторов время выборки наиболее релевантных результатов укладывается в 8 мс.
В состав библиотеки включены средства для построения индекса и организации поиска векторов, а также набор инструментов для сопровождения распределённой системы online-поиска, охватывающей очень большие коллекции векторов. Предлагаются следующие модули: index builder для индексации, searcher для поиска с использованием индекса, распределённого в кластере из нескольких узлов, сервер для запуска обработчиков на узлах, Aggregator для объединения нескольких серверов в одно целое и клиент для отправки запросов. Поддерживается включение новых векторов в индекс и удаление векторов на лету.
Библиотека подразумевает, что обрабатываемые и представленные в коллекции данные оформлены в виде связанных векторов, которые можно сравнивать на основе евклидовых (L2) или косинусных расстояний. При поисковом запросе возвращаются векторы, расстояние между которыми и исходным вектором минимально. В SPTAG предоставляется два метода организации векторного пространства: SPTAG-KDT (K-мерное дерево (kd-tree) и граф относительных окрестностей) и SPTAG-BKT (дерево k-средних (k-means tree и граф относительных окрестностей). Первый метод требует меньше ресурсов при работе с индексом, а второй демонстрирует более высокую точность результатов поиска при очень больших коллекциях векторов.
При этом векторный поиск не ограничивается текстом и может применяться к мультимедийной информации и изображениям, а также для в системах автоматического формирования рекомендаций. Например, в одном из прототипов на базе фреймворка PyTorch была реализована векторная система для поиска с учётом сходства объектов на изображениях, построенная с использованием данных из нескольких эталонных коллекций с изображениями животных, кошек и собак, которые были преобразованы в наборы векторов. При поступлении входящего изображения для поиска оно преобразуется с использованием модели машинного обучения в вектор, на основе которого при помощи алгоритма SPTAG из индекса выбираются наиболее похожие векторы и как результат возвращаются связанные с ними изображения.