FARGO: быстрый поиск максимального скалярного произведения с помощью глобального мультизондирования

01/01/2023

Понимание поиска максимального скалярного произведения: от теории к практике

По мере того как машинное обучение и искусственный интеллект продолжают развиваться, способность эффективно осуществлять поиск в многомерных векторных пространствах становится все более важной. Одной из фундаментальных задач в этой области является проблема поиска максимального скалярного произведения (Maximum Inner Product Search, MIPS), которая заключается в нахождении векторов в наборе данных, максимизирующих их скалярное произведение с заданным вектором запроса. Эта операция играет ключевую роль во множестве приложений, включая рекомендательные системы, предсказание меток для нескольких классов, поиск похожих элементов, структурные SVM и глубокое обучение.

Традиционные подходы к MIPS, использующие деревья разбиения пространства, становятся экспоненциально медленнее по мере увеличения размерности, что делает их непрактичными для современных приложений, которые часто работают с сотнями или тысячами измерений. Хотя локально-чувствительное хеширование (Locality-Sensitive Hashing, LSH) доказало свою эффективность для приближенного поиска ближайших соседей, оно не может быть напрямую применено к MIPS из-за уникальных свойств сходства на основе скалярного произведения. Потребность в эффективном, масштабируемом решении для MIPS стала как никогда актуальной, поскольку организации обрабатывают все более крупномасштабные многомерные наборы данных.

В этой статье представлена FARGO — новая платформа, которая кардинально меняет наш подход к проблеме MIPS. Мы представляем всесторонний анализ существующих решений MIPS, их ограничений и того, как FARGO преодолевает эти трудности с помощью инновационных методов, включая глобальное мультизондирование и случайное преобразование XBOX. Наша платформа не только обеспечивает более высокую точность и эффективность по сравнению с существующими методами, но и предлагает практические решения для реальных приложений, работающих с многомерными данными в больших масштабах.

Получить Белую книгу