Busca Eficiente e Robusta de Similaridade Vetorial Fora da Distribuição com Grafo Monótono de Cruzamento de Distribuições

A busca de similaridade vetorial é um componente chave em muitas aplicações de IA. Embora métodos baseados em grafos representem o estado da arte para busca de similaridade vetorial, índices de grafos existentes frequentemente sofrem com navegabilidade e capacidade de agrupamento pobres em cenários Fora-da-Distribuição (OOD) (por exemplo, banco de dados e consultas provenientes de modalidades diferentes). Estudos recentes tentaram mitigar essa questão projetando e integrando estruturas de índices auxiliares derivadas de consultas, mas essas abordagens permanecem amplamente heurísticas e carecem de fundamentação teórica. Neste trabalho, propomos o Grafo Monótono de Cruzamento de Distribuição (CDMG), um índice de grafo inovador projetado para suportar inerentemente navegabilidade e capacidade de agrupamento para consultas OOD. O CDMG introduz uma estratégia de integração que supera a lacuna de distribuição entre vetores do banco de dados e das consultas, garantindo uma propriedade chave — monotonicidade cruzada de distribuição — que assegura caminhos de busca monotônicos para consultas OOD em índices de grafos. A análise teórica demonstra que o CDMG alcança uma complexidade de tempo de busca mais baixa em cenários OOD comparado com índices de grafos existentes. Além disso, apresentamos o CDMG+, uma variante prática do CDMG que melhora a eficiência de construção ao introduzir síntese de consultas, computação de distância baseada em fusão, bem como estratégias otimizadas de aquisição de candidatos e seleção de vizinhos. Avaliações empíricas extensas demonstram que nossas técnicas superam métodos de última geração, alcançando até 3,6× de aceleração em conjuntos de dados OOD do mundo real.