El algoritmo de búsqueda vectorial de Zilliz domina las cuatro categorías de BigANN
El desafío BigANN es una competición culminante en el ámbito de la búsqueda vectorial, que fomenta el desarrollo de estructuras de datos de indexación y algoritmos de búsqueda para variantes prácticas del problema de Vecino Más Cercano Aproximado (ANN). Zilliz se enorgullece de ser un organizador clave de esta importante competición, siendo testigo de soluciones ingeniosas de participantes de todo el mundo. Como creadores de la base de datos vectorial Milvus, nos sentimos obligados a aportar nuestras perspectivas y soluciones al desafío planteado.
Hoy, nos complace compartir una gran noticia: nuestra solución de Zilliz superó todas las presentaciones existentes y las soluciones de otros proveedores en las cuatro pistas de BigANN, logrando una notable mejora de rendimiento de hasta 2,5 veces. Esta publicación presentará BigANN 2023 y profundizará en la solución de Zilliz y sus resultados de rendimiento.
BigANN 2023
El benchmark ANN es una herramienta estándar de la industria para evaluar algoritmos de búsqueda vectorial, pero sus conjuntos de datos de evaluación de pequeño tamaño limitan su aplicabilidad a desafíos de producción del mundo real. En respuesta, nació BigANN, que sirve tanto como competición como iniciativa de benchmarking, abordando esta limitación mediante la evaluación y el avance de algoritmos en conjuntos de datos a gran escala.
Este año, BigANN 2023 introduce desafíos más significativos, haciendo hincapié en conjuntos de datos más grandes (hasta 10 millones de puntos vectoriales) y escenarios más complejos. La competición cuenta con cuatro pistas: variantes filtradas, fuera de distribución, dispersas y de streaming de ANNS, proporcionando un campo de pruebas realista para escenarios del mundo real.
Tabla1: Las cuatro pistas de BigANN 2023
Pista filtrada: Esta tarea utiliza el conjunto de datos YFCC 100M, seleccionando 10 millones de imágenes. Requiere extraer embeddings CLIP para cada imagen y generar etiquetas que cubran aspectos como la descripción de la imagen, el modelo de cámara, el año de captura y el país, extraídos de un vocabulario diverso. El desafío aquí es emparejar de manera competente 100.000 consultas, cada una compuesta por un embedding de imagen y etiquetas específicas, con sus imágenes y etiquetas correspondientes en el conjunto de datos.
Pista fuera de distribución(OOD): Esta pista presenta a los participantes el conjunto de datos Yandex Text-to-Image 10M, destacando la integración de datos multimodales. El conjunto de datos base incluye 10 millones de embeddings de imágenes de la base de datos de búsqueda visual de Yandex, generados utilizando el modelo Se-ResNext-101. En cambio, los embeddings de consulta se basan en búsquedas textuales, procesadas mediante un modelo diferente. El desafío principal aquí es cerrar eficazmente la brecha entre estas diferentes modalidades de datos.
Pista dispersa: Esta pista aprovecha el conjunto de datos de recuperación de pasajes MSMARCO, que presenta una extensa colección de más de 8,8 millones de pasajes de texto codificados en vectores dispersos utilizando el modelo SPLADE. Estos vectores tienen alrededor de 30.000 dimensiones, pero presentan una naturaleza dispersa. Al mismo tiempo, las casi 7.000 consultas se procesan mediante el mismo modelo, aunque con menos elementos distintos de cero debido a su longitud concisa. La tarea principal en esta pista es recuperar con precisión los mejores resultados para una consulta determinada, con un énfasis específico en el producto interno máximo entre los vectores de consulta y los vectores de la base de datos.
Pista de streaming: Esta pista se basa en un segmento del conjunto de datos MS Turing, compuesto por 30 millones de puntos de datos. Los participantes deben seguir un "runbook" proporcionado que describe intrincadamente una secuencia de operaciones de inserción, eliminación y búsqueda de datos. Estas operaciones deben completarse en una hora y con menos de 8 GB de DRAM. Esta pista se centra en optimizar el proceso de gestión de estas operaciones y en mantener un índice optimizado del conjunto de datos.
En esta competición, cada pista tiene criterios distintos para la clasificación de algoritmos:
En las pistas Filters, OOD y Sparse, los algoritmos se evalúan según QPS, siempre que alcancen un mínimo de 90% de recall@10.
En la pista Streaming, los algoritmos se clasifican según recall@10, con el requisito adicional de completar el runbook en una hora.
Todas las pruebas de rendimiento, incluida nuestra solución de Zilliz, se realizaron en una Azure D8lds_v5 (8 vCPU y 16 GiB de memoria).
Solución de Zilliz y sus resultados de rendimiento
Todos los resultados siguientes se adhieren al marco de evaluación y a las directrices establecidas por la competencia BigANN, lo que garantiza una comparación justa y exhaustiva.
Pista Filtered
Comparación de nuestra solución para la pista Filter (zilliz) frente a la línea base oficial (faiss), el ganador (parlayivf) y la solución de Pinecone. Con un 90% de recall, nuestro rendimiento es de aproximadamente 82.000 QPS, alrededor de 25 veces la línea base de 3.200 QPS, 2,5 veces el ganador de la pista con 32.000 QPS, y mucho más alto que la solución de Pinecone con 68.000 QPS.
Nuestra solución se basa en algoritmos de grafos y clasificación de etiquetas. Durante la fase de construcción, analizamos la cardinalidad de cada combinación potencial de etiquetas. Construimos grafos para combinaciones con una gran cantidad de vectores, al tiempo que establecemos índices invertidos para las demás. Al buscar, elegimos el método de búsqueda adecuado según las características únicas de cada combinación de etiquetas.
En paralelo, clasificamos las consultas según sus etiquetas asociadas. Durante la búsqueda, buscamos cada consulta en función de su etiqueta correspondiente. Este enfoque ofrece dos beneficios: 1) maximiza el uso de la caché, y 2) permite la aceleración mediante multiplicación de matrices, lo que es particularmente beneficioso durante las búsquedas exhaustivas.
Cuantizamos los datos para acelerar los cálculos y usamos SIMD para ajustar los cálculos de distancia, garantizando una alta eficiencia computacional.
Pista OOD
Comparación de nuestra solución para la pista OOD frente a la línea base oficial (diskann), el ganador de la pista (pyanns) y la solución de Pinecone (pinecone-odd). Con un 90% de recall, nuestro rendimiento es de aproximadamente 33.000 QPS, 8 veces la línea base de alrededor de 4.000 QPS y supera al ganador de la pista con aproximadamente 23.000 QPS y a la solución de Pinecone con 26.000 QPS.
Nota: Realizamos esta comparación utilizando el conjunto de consultas público, ya que no hay un conjunto de consultas oculto en esta pista.
Nuestra solución se basa en la sinergia de algoritmos de grafos y un proceso de búsqueda altamente optimizado.
Para el cálculo, usamos cuantización en diferentes niveles de precisión tanto para la búsqueda como para el refinamiento, y aprovechamos la potencia de SIMD para cálculos acelerados. Antes de buscar, agrupamos los vectores de consulta. Durante la búsqueda en grafos, a cada clúster de consultas se le asignan puntos iniciales distintos, allanando el camino para búsquedas secuenciales dentro de cada clúster.
Esta estrategia de clustering tiene dos ventajas: 1) una exploración secuencial de diferentes clústeres maximiza la utilización de la caché, y 2) la asignación de puntos iniciales adaptativos a diversos clústeres mitiga los desafíos derivados de distribuciones variables de vectores.
Además, también implementamos una estructura de datos bitset multinivel. Necesitamos una estructura de datos para marcar los puntos visitados en el complejo proceso de búsqueda de imágenes. Los métodos convencionales a menudo recurren a un bitset o a una tabla hash, pero cada uno tiene inconvenientes. Los bitsets a menudo provocan un uso ineficiente de la memoria y fallos de caché, mientras que las tablas hash funcionan mal debido a constantes desfavorables. Hemos innovado una estructura de datos bitset multinivel que se inspira en las tablas de páginas multinivel en memoria. Este diseño optimiza la utilización de la caché de la CPU, lo que resulta en una mejora significativa del rendimiento de lectura y escritura.
Pista Sparse
Comparación de nuestra solución para la pista Sparse (zilliz) con la línea base oficial (linscan), el ganador de la pista (pyanns) y la solución de Pinecone (pinecone_smips). Con un recall del 90%, nuestro throughput es de alrededor de 8,200 QPS, lo que equivale a 82 veces la línea base de alrededor de 100 QPS, y superó tanto al ganador de la pista con 6,000 QPS como a la solución de Pinecone con 7,400 QPS.
En esta pista, nuestra solución se basa en la sinergia de algoritmos de grafos y optimizaciones impulsadas por vectores dispersos. Cada vector disperso se representa como una lista de tuplas (data[float32], index[int32]). Introducimos cuantización de precisión múltiple para procesar los datos, atendiendo a los cálculos durante la búsqueda en grafos y el refinamiento posterior. Además, optimizamos el ancho de banda de memoria representando el índice mediante int16.
La tarea consiste en maximizar la búsqueda de producto interno. En los cálculos de producto interno, sus magnitudes influyen en la importancia de los valores. Las magnitudes mayores tienen mayor relevancia, mientras que las menores son menos importantes. Aprovechando esta idea, implementamos una estrategia de poda durante la búsqueda en grafos, descartando valores con magnitudes absolutas más pequeñas. Tras la búsqueda en grafos, realizamos un refinamiento usando los vectores completos. Los resultados experimentales indican que podemos podar más del 80% de los datos en los vectores de consulta sin comprometer significativamente el recall.
Empleamos tecnología SIMD para la intersección rápida de listas ordenadas con el fin de realizar cálculos expeditivos, logrando así cálculos altamente eficientes para productos internos de vectores dispersos.
Pista Streaming
Comparación de nuestra solución para la pista Streaming (zilliz) con la línea base oficial (diskann), el ganador de la pista (puck) y la solución de Pinecone (pinecone). Nuestro algoritmo alcanza un recall de 0.9982, superando al ganador de la pista y a la solución de Pinecone, con recalls de 0.986 y 0.9975, respectivamente.
Nuestra solución para la pista streaming se basa en algoritmos de grafos y cuantización SQ.
Implementamos una estrategia de eliminación diferida para las operaciones de eliminación, marcando vectores para su eliminación sin cambiar inmediatamente la estructura del grafo. El grafo no se reestructura hasta que se acumula un número especificado de operaciones de eliminación.
Cuantizamos vectores con varias precisiones tanto para la búsqueda en grafos como para el refinamiento. Primero, usamos vectores de menor precisión para la búsqueda en grafos. Sin embargo, debido a nuestra estrategia de eliminación diferida, los vectores eliminados pueden aparecer en los resultados de búsqueda. Por lo tanto, aprovechamos una estrategia de posfiltrado para eliminar estos vectores eliminados. Finalmente, usamos vectores cuantizados de mayor precisión para refinar los resultados.
Nota: Si bien nuestra solución no es open-sourced, hemos explicado nuestra metodología y publicado los binarios en el repo de GitHub de BigANN para una amplia accesibilidad y reproducción.
Los algoritmos de BigANN se integrarán en los productos de Zilliz
A medida que avanza la IA, la búsqueda vectorial se ha vuelto esencial para dar soporte a escenarios de producción complejos. La cobertura de BigANN de múltiples escenarios añade un valor práctico significativo. Estamos encantados de participar activamente en esta competición de BigANN y disfrutamos abordando estos desafiantes problemas algorítmicos. Incorporaremos los aprendizajes de este proceso en nuestros productos, ampliando su impacto a una gama más amplia de problemas.
¡Ven y únete a nosotros!
En Zilliz, estamos comprometidos con construir la mejor base de datos vectorial del mundo, usando la búsqueda vectorial para abordar problemas del mundo real. También estamos en un viaje continuo explorando casos de uso desafiantes inspirados por BigANN y más allá. Invitamos a personas con intereses afines en búsqueda vectorial, sistemas de bases de datos o tecnologías de IA a unirse a nosotros en este camino. Si te interesa, ¡ponte en contacto! Explora oportunidades en nuestra página de career para obtener más información y postularte.
Esta publicación está escrita por Li Liu y Zihao Wang.
Sigue leyendo
How to Install and Run OpenClaw (Previously Clawdbot/Moltbot) on Mac
Turn your Mac into an AI gateway for WhatsApp, Telegram, Discord, iMessage, and more — in under 5 minutes.
Migrating from S3 Vectors to Zilliz Cloud: Unlocking the Power of Tiered Storage
Learn how Zilliz Cloud bridges cost and performance with tiered storage and enterprise-grade features, and how to migrate data from AWS S3 Vectors to Zilliz Cloud.
Our Journey to 35K+ GitHub Stars: The Real Story of Building Milvus from Scratch
Join us in celebrating Milvus, the vector database that hit 35.5K stars on GitHub. Discover our story and how we’re making AI solutions easier for developers.