Algoritmo de Busca Vetorial da Zilliz Domina Todas as Quatro Trilhas do BigANN
O desafio BigANN é uma competição culminante no domínio da busca vetorial, promovendo o desenvolvimento de estruturas de dados de indexação e algoritmos de busca para variantes práticas do problema do Vizinho Mais Próximo Aproximado (ANN). A Zilliz se orgulha de ser uma das principais organizadoras desta importante competição, testemunhando soluções engenhosas de participantes globais. Como criadores do banco de dados vetorial Milvus, sentimos a necessidade de contribuir com nossos insights e soluções para o desafio apresentado.
Hoje, estamos entusiasmados em compartilhar uma ótima notícia: nossa solução da Zilliz superou todas as submissões existentes e soluções de outros fornecedores em todas as quatro trilhas do BigANN, alcançando uma melhoria de desempenho notável de até 2,5x. Este post apresentará o BigANN 2023 e se aprofundará na solução da Zilliz e em seus resultados de desempenho.
BigANN 2023
O benchmark ANN é uma ferramenta padrão da indústria para avaliar algoritmos de busca vetorial, mas seus conjuntos de dados de avaliação de pequeno porte limitam sua aplicabilidade a desafios reais de produção. Em resposta, o BigANN nasceu e serve tanto como uma competição quanto como uma iniciativa de benchmarking, abordando essa limitação ao avaliar e avançar algoritmos em conjuntos de dados de larga escala.
Este ano, o BigANN 2023 introduz desafios mais significativos, enfatizando conjuntos de dados maiores (até 10 milhões de pontos vetoriais) e cenários mais complexos. A competição apresenta quatro trilhas: variantes filtrada, fora da distribuição, esparsa e streaming de ANNS, fornecendo um campo de testes realista para cenários do mundo real.
Table1: As quatro trilhas do BigANN 2023
Trilha Filtrada: Esta tarefa usa o conjunto de dados YFCC 100M, selecionando 10 milhões de imagens. Ela exige a extração de embeddings CLIP para cada imagem e a geração de tags que abrangem aspectos como descrição da imagem, modelo da câmera, ano de captura e país, extraídos de um vocabulário diverso. O desafio aqui é corresponder com proficiência 100.000 consultas, cada uma composta por um embedding de imagem e tags específicas, às suas imagens e tags correspondentes no conjunto de dados.
Trilha Fora da Distribuição(OOD): Esta trilha apresenta aos participantes o conjunto de dados Yandex Text-to-Image 10M, destacando a integração de dados multimodais. O conjunto de dados base inclui 10 milhões de embeddings de imagens do banco de dados de busca visual da Yandex, gerados usando o modelo Se-ResNext-101. Em contraste, os embeddings de consulta são baseados em buscas textuais, processadas por meio de um modelo diferente. O principal desafio aqui é preencher efetivamente a lacuna entre essas diferentes modalidades de dados.
Trilha Esparsa: Esta trilha aproveita o conjunto de dados de recuperação de passagens MSMARCO, apresentando uma extensa coleção de mais de 8,8 milhões de passagens de texto codificadas em vetores esparsos usando o modelo SPLADE. Esses vetores têm cerca de 30.000 dimensões, mas exibem uma natureza esparsa. Simultaneamente, as quase 7.000 consultas são processadas pelo mesmo modelo, embora com menos elementos diferentes de zero devido ao seu comprimento conciso. A principal tarefa nesta trilha é recuperar com precisão os principais resultados para uma determinada consulta, com uma ênfase específica no produto interno máximo entre os vetores de consulta e os vetores do banco de dados.
Trilha Streaming: Esta trilha é baseada em um segmento do conjunto de dados MS Turing, compreendendo 30 milhões de pontos de dados. Os participantes precisam seguir um "runbook" fornecido, que delineia de forma intrincada uma sequência de operações de inserção, exclusão e busca de dados. Essas operações devem ser concluídas em até uma hora e com menos de 8GB de DRAM. Esta trilha foca na otimização do processo de tratamento dessas operações e na manutenção de um índice simplificado do conjunto de dados.
Nesta competição, cada trilha tem critérios distintos para a classificação dos algoritmos:
Nas trilhas Filters, OOD e Sparse, os algoritmos são avaliados com base em QPS, desde que alcancem um mínimo de 90% de recall@10.
Na trilha Streaming, os algoritmos são classificados de acordo com o recall@10, com o requisito adicional de concluir o runbook em até uma hora.
Todos os testes de desempenho, incluindo nossa solução Zilliz, foram conduzidos em uma Azure D8lds_v5 (8 vCPUs e 16 GiB de memória).
Solução da Zilliz e seus resultados de desempenho
Todos os resultados a seguir seguem a estrutura de avaliação e as diretrizes estabelecidas pela competição BigANN, garantindo uma comparação justa e abrangente.
Trilha Filtered
Comparação da nossa solução da trilha Filter (zilliz) com a baseline oficial (faiss), o vencedor (parlayivf) e a solução da Pinecone. Com 90% de recall, nosso throughput é de aproximadamente 82.000 QPS, cerca de 25x a baseline de 3.200 QPS, 2,5x o vencedor da trilha com 32.000 QPS e muito superior à solução da Pinecone com 68.000 QPS.
Nossa solução é baseada em algoritmos de grafos e classificação de tags. Durante a fase de construção, analisamos a cardinalidade de cada combinação potencial de tags. Construímos grafos para combinações com um grande número de vetores, ao mesmo tempo em que estabelecemos índices invertidos para outras. Ao pesquisar, escolhemos o método de busca apropriado com base nas características únicas de cada combinação de tags.
Em paralelo, classificamos as consultas de acordo com suas tags associadas. Durante a busca, pesquisamos cada consulta com base em sua tag correspondente. Essa abordagem oferece dois benefícios: 1) maximiza o uso do cache e 2) permite aceleração por meio de multiplicação de matrizes, o que é particularmente benéfico durante buscas exaustivas.
Quantizamos os dados para acelerar os cálculos e usamos SIMD para ajustar finamente os cálculos de distância, garantindo alta eficiência computacional.
Trilha OOD
Comparação da nossa solução da trilha OOD com a baseline oficial (diskann), o vencedor da trilha (pyanns) e a solução da Pinecone (pinecone-odd). Com 90% de recall, nosso throughput é de aproximadamente 33.000 QPS, 8x a baseline de cerca de 4.000 QPS, e supera o vencedor da trilha, com aproximadamente 23.000 QPS, e a solução da Pinecone, com 26.000 QPS.
Observação: Fazemos esta comparação usando o conjunto público de consultas, já que não há conjunto oculto de consultas nesta trilha.
Nossa solução é baseada na sinergia entre algoritmos de grafos e um processo de busca altamente otimizado.
Para computação, usamos quantização em diferentes níveis de precisão tanto para busca quanto para refinamento e aproveitamos o poder do SIMD para cálculos acelerados. Antes da busca, agrupamos vetores de consulta. Durante a busca em grafo, cada cluster de consultas recebe pontos iniciais distintos, abrindo caminho para buscas sequenciais dentro de cada cluster.
Essa estratégia de clustering tem duas vantagens: 1) uma exploração sequencial de diferentes clusters maximiza a utilização do cache e 2) a alocação de pontos iniciais adaptativos a clusters diversos mitiga desafios decorrentes de distribuições variáveis de vetores.
Além disso, também implementamos uma estrutura de dados bitset multinível. Precisamos de uma estrutura de dados para marcar pontos visitados no intrincado processo de busca de imagens. Métodos convencionais frequentemente recorrem a um bitset ou a uma tabela hash, mas cada um tem desvantagens. Bitsets frequentemente levam a uso ineficiente de memória e cache misses, enquanto tabelas hash têm desempenho ruim devido a constantes desfavoráveis. Inovamos com uma estrutura de dados bitset multinível que se inspira em tabelas de páginas multinível na memória. Esse design otimiza a utilização do cache da CPU, resultando em uma melhoria significativa no desempenho de leitura e escrita.
Trilha Sparse
Comparação da nossa solução da trilha Sparse (zilliz) com a baseline oficial (linscan), o vencedor da trilha (pyanns) e a solução da Pinecone (pinecone_smips). Com 90% de recall, nosso throughput é de cerca de 8.200 QPS, o que é 82x a baseline de cerca de 100 QPS, e superou tanto o vencedor da trilha, com 6.000 QPS, quanto a solução da Pinecone, com 7.400 QPS.
Nesta trilha, nossa solução é baseada na sinergia de algoritmos de grafos e otimizações impulsionadas por vetores esparsos. Cada vetor esparso é representado como uma lista de tuplas (data[float32], index[int32]). Introduzimos quantização de múltipla precisão para processar os dados, atendendo aos cálculos durante a busca em grafos e ao refinamento subsequente. Além disso, otimizamos a largura de banda da memória representando o índice usando int16.
A tarefa trata de maximizar a busca por produto interno. Nos cálculos de produto interno, suas magnitudes influenciam a importância dos valores. Magnitudes maiores têm maior significância, enquanto as menores são menos importantes. Aproveitando esse insight, implementamos uma estratégia de poda durante a busca em grafos, descartando valores com magnitudes absolutas menores. Após a busca em grafos, conduzimos o refinamento usando os vetores completos. Resultados experimentais indicam que podemos podar mais de 80% dos dados nos vetores de consulta sem comprometer significativamente o recall.
Empregamos tecnologia SIMD para a interseção rápida de listas ordenadas para cálculos expeditos, alcançando assim cálculos altamente eficientes para produtos internos de vetores esparsos.
Trilha Streaming
Comparação da nossa solução da trilha Streaming (zilliz) com a baseline oficial (diskann), o vencedor da trilha (puck) e a solução da Pinecone (pinecone). Nosso algoritmo atinge um recall de 0,9982, superando o vencedor da trilha e a solução da Pinecone, com recalls de 0,986 e 0,9975, respectivamente.
Nossa solução da trilha streaming é baseada em algoritmos de grafos e quantização SQ.
Implementamos uma estratégia de exclusão preguiçosa para operações de exclusão, marcando vetores para exclusão sem alterar imediatamente a estrutura do grafo. O grafo não é reestruturado até que um número especificado de operações de exclusão se acumule.
Quantizamos vetores em várias precisões tanto para a busca em grafos quanto para o refinamento. Primeiro, usamos vetores de menor precisão para a busca em grafos. No entanto, devido à nossa estratégia de exclusão preguiçosa, vetores excluídos podem aparecer nos resultados da busca. Então, aproveitamos uma estratégia de pós-filtragem para eliminar esses vetores excluídos. Por fim, usamos vetores quantizados de maior precisão para refinar os resultados.
Observação: Embora nossa solução não seja open-sourced, explicamos nossa metodologia e lançamos os binários no repo GitHub da BigANN para ampla acessibilidade e reprodução.
Os algoritmos BigANN serão integrados aos produtos da Zilliz
À medida que a IA avança, a busca vetorial tornou-se essencial para dar suporte a cenários complexos de produção. A cobertura da BigANN de múltiplos cenários agrega valor prático significativo. Estamos entusiasmados por estar ativamente envolvidos nesta competição BigANN e gostamos de enfrentar esses desafiadores problemas algorítmicos. Incorporaremos os insights desse processo aos nossos produtos, ampliando seu impacto em uma gama mais ampla de questões.
Venha se juntar a nós!
Na Zilliz, estamos comprometidos em construir o melhor banco de dados vetorial do mundo, usando busca vetorial para resolver problemas do mundo real. Também estamos em uma jornada contínua explorando casos de uso desafiadores inspirados pela BigANN e além. Estamos convidando pessoas com interesses semelhantes em busca vetorial, sistemas de banco de dados ou tecnologias de IA a se juntarem a nós nesse caminho. Se você tiver interesse, entre em contato! Explore oportunidades em nossa página de carreiras para mais informações e para se candidatar.
Este post foi escrito por Li Liu e Zihao Wang.
Continue lendo
Why Teams Are Migrating from Weaviate to Zilliz Cloud — and How to Do It Seamlessly
Explore how Milvus scales for large datasets and complex queries with advanced features, and discover how to migrate from Weaviate to Zilliz Cloud.
How to Build an Enterprise-Ready RAG Pipeline on AWS with Bedrock, Zilliz Cloud, and LangChain
Build production-ready enterprise RAG with AWS Bedrock, Nova models, Zilliz Cloud, and LangChain. Complete tutorial with deployable code.
Build for the Boom: Why AI Agent Startups Should Build Scalable Infrastructure Early
Explore strategies for developing AI agents that can handle rapid growth. Don't let inadequate systems undermine your success during critical breakthrough moments.