FARGO: Busca Rápida do Produto Interno Máximo via Multi-Sondagem Global

01/01/2023

Entendendo a Busca de Produto Interno Máximo: Da Teoria à Prática

À medida que o aprendizado de máquina e a inteligência artificial continuam a avançar, a capacidade de pesquisar eficientemente em espaços vetoriais de alta dimensionalidade tornou-se cada vez mais crucial. Um desafio fundamental nesse domínio é o problema de Busca de Produto Interno Máximo (MIPS), que envolve encontrar vetores em um conjunto de dados que maximizem seu produto interno com um determinado vetor de consulta. Essa operação é central para inúmeras aplicações, incluindo sistemas de recomendação, previsão de rótulos multiclasse, recuperação de itens semelhantes, SVM estrutural e aprendizado profundo.

Abordagens tradicionais para MIPS usando árvores de particionamento do espaço tornam-se exponencialmente mais lentas à medida que a dimensionalidade aumenta, tornando-as impraticáveis para aplicações modernas que frequentemente lidam com centenas ou milhares de dimensões. Embora o Hashing Sensível à Localidade (LSH) tenha se mostrado eficaz para busca aproximada de vizinho mais próximo, ele não pode ser aplicado diretamente a MIPS devido às propriedades únicas da similaridade por produto interno. A necessidade de uma solução eficiente e escalável para MIPS nunca foi tão urgente, à medida que as organizações processam conjuntos de dados cada vez maiores, em grande escala e de alta dimensionalidade.

Este artigo apresenta FARGO, um novo framework que revoluciona a forma como abordamos o problema de MIPS. Apresentamos uma análise abrangente das soluções atuais de MIPS, suas limitações e como o FARGO supera esses desafios por meio de técnicas inovadoras, incluindo multi-probing global e transformação XBOX aleatória. Nosso framework não apenas alcança precisão e eficiência superiores em comparação com métodos existentes, mas também fornece soluções práticas para aplicações do mundo real que lidam com dados de alta dimensionalidade em escala.

Obter o Whitepaper