Алгоритм векторного поиска Zilliz доминирует во всех четырех направлениях BigANN
Соревнование BigANN — это кульминационный конкурс в области векторного поиска, способствующий развитию индексирующих структур данных и поисковых алгоритмов для практических вариантов задачи приближенного ближайшего соседа (ANN). Zilliz гордится тем, что является одним из ключевых организаторов этого значимого соревнования и наблюдает за оригинальными решениями участников со всего мира. Как создатели векторной базы данных Milvus, мы почувствовали необходимость внести свой вклад, поделившись нашими идеями и решениями для представленной задачи.
Сегодня мы рады поделиться отличной новостью: наше решение Zilliz превзошло все существующие заявки и решения других поставщиков во всех четырех треках BigANN, достигнув впечатляющего улучшения производительности до 2,5 раз. В этой статье мы представим BigANN 2023 и подробно рассмотрим решение Zilliz и его результаты производительности.
BigANN 2023
ANN benchmark — это отраслевой стандартный инструмент для оценки алгоритмов векторного поиска, однако небольшие оценочные наборы данных ограничивают его применимость к реальным производственным задачам. В ответ на это появился BigANN, который служит как соревнованием, так и инициативой по бенчмаркингу, устраняя это ограничение путем оценки и развития алгоритмов на крупномасштабных наборах данных.
В этом году BigANN 2023 представляет более значительные вызовы, делая акцент на более крупных наборах данных (до 10 миллионов векторных точек) и более сложных сценариях. Соревнование включает четыре трека: filtered, out-of-distribution, sparse и streaming варианты ANNS, предоставляя реалистичную испытательную площадку для сценариев из реального мира.
Table1: Четыре трека BigANN 2023
Filtered Track: В этой задаче используется набор данных YFCC 100M, из которого выбираются 10 миллионов изображений. Она требует извлечения CLIP embeddings для каждого изображения и генерации тегов, охватывающих такие аспекты, как описание изображения, модель камеры, год съемки и страна, взятых из разнообразного словаря. Сложность здесь заключается в том, чтобы эффективно сопоставить 100 000 запросов, каждый из которых включает embedding изображения и конкретные теги, с соответствующими изображениями и тегами в наборе данных.
Out-Of-Distribution(OOD) Track: Этот трек предоставляет участникам набор данных Yandex Text-to-Image 10M, подчеркивая интеграцию кросс-модальных данных. Базовый набор данных включает 10 миллионов embeddings изображений из базы данных визуального поиска Yandex, сгенерированных с использованием модели Se-ResNext-101. В отличие от этого, embeddings запросов основаны на текстовых поисковых запросах, обработанных с помощью другой модели. Основная задача здесь — эффективно преодолеть разрыв между этими различными модальностями данных.
Sparse Track: Этот трек использует набор данных MSMARCO passage retrieval, содержащий обширную коллекцию из более чем 8,8 миллиона текстовых фрагментов, закодированных в разреженные векторы с использованием модели SPLADE. Эти векторы имеют около 30 000 измерений, но обладают разреженной природой. Одновременно почти 7 000 запросов обрабатываются той же моделью, хотя и с меньшим количеством ненулевых элементов из-за их краткой длины. Основная задача в этом треке — точно извлечь лучшие результаты для заданного запроса, с особым акцентом на максимальном скалярном произведении между векторами запросов и векторами базы данных.
Streaming Track: Этот трек основан на сегменте набора данных MS Turing, включающем 30 миллионов точек данных. Участникам необходимо следовать предоставленному "runbook", который подробно описывает последовательность операций вставки, удаления и поиска данных. Эти операции должны быть выполнены в течение часа и при использовании менее 8GB DRAM. Этот трек сосредоточен на оптимизации процесса обработки этих операций и поддержании оптимизированного индекса набора данных.
В этом соревновании каждый трек имеет отдельные критерии ранжирования алгоритмов:
В треках Filters, OOD и Sparse алгоритмы оцениваются на основе QPS при условии, что они достигают минимума в 90% recall@10.
В Streaming track алгоритмы ранжируются по recall@10 с дополнительным требованием завершить runbook в течение часа.
Все тесты производительности, включая наше решение Zilliz, проводились на Azure D8lds_v5 (8 vCPU и 16 GiB памяти).
Решение Zilliz и его результаты производительности
Все следующие результаты соответствуют фреймворку оценки и рекомендациям, установленным соревнованием BigANN, обеспечивая справедливое и всестороннее сравнение.
Filtered Track
Сравнение нашего решения для Filter track (zilliz) с официальным baseline (faiss), победителем (parlayivf) и решением Pinecone. При 90% recall наша пропускная способность составляет примерно 82 000 QPS, что приблизительно в 25 раз выше baseline на уровне 3 200 QPS, в 2,5 раза выше победителя трека на уровне 32 000 QPS и значительно выше решения Pinecone на уровне 68 000 QPS.
Наше решение основано на графовых алгоритмах и классификации тегов. На этапе построения мы анализируем кардинальность каждой потенциальной комбинации тегов. Мы строим графы для комбинаций с большим количеством векторов, одновременно создавая инвертированные индексы для остальных. При поиске мы выбираем подходящий метод поиска на основе уникальных характеристик каждой комбинации тегов.
Параллельно мы классифицируем запросы согласно связанным с ними тегам. Во время поиска мы выполняем поиск для каждого запроса на основе соответствующего ему тега. Такой подход дает два преимущества: 1) он максимизирует использование кэша, и 2) он обеспечивает ускорение за счет матричного умножения, что особенно полезно при исчерпывающем поиске.
Мы квантуем данные для ускорения вычислений и используем SIMD для тонкой настройки вычислений расстояний, обеспечивая высокую вычислительную эффективность.
OOD Track
Сравнение нашего решения для OOD track с официальным baseline (diskann), победителем трека (pyanns) и решением Pinecone (pinecone-odd). При 90% recall наша пропускная способность составляет примерно 33 000 QPS, что в 8 раз выше baseline на уровне около 4 000 QPS, и превосходит победителя трека на уровне приблизительно 23 000 QPS и решение Pinecone на уровне 26 000 QPS.
Примечание: Мы проводим это сравнение с использованием публичного набора запросов, поскольку в этом треке нет скрытого набора запросов.
Наше решение основано на синергии графовых алгоритмов и высокооптимизированного процесса поиска.
Для вычислений мы используем квантизацию на разных уровнях точности как для поиска, так и для уточнения, а также задействуем возможности SIMD для ускоренных вычислений. Перед поиском мы кластеризуем векторы запросов. Во время графового поиска каждому кластеру запросов назначаются отдельные начальные точки, что открывает путь для последовательных поисков внутри каждого кластера.
Эта стратегия кластеризации имеет два преимущества: 1) последовательное исследование разных кластеров максимизирует использование кэша, и 2) выделение адаптивных начальных точек разнообразным кластерам снижает сложности, возникающие из-за различающихся распределений векторов.
Кроме того, мы также реализуем многоуровневую структуру данных bitset. Нам нужна структура данных для отметки посещенных точек в сложном процессе поиска изображений. Традиционные методы часто прибегают к bitset или хеш-таблице, но у каждого подхода есть недостатки. Bitset часто приводит к неэффективному использованию памяти и промахам кэша, тогда как хеш-таблицы показывают низкую производительность из-за неблагоприятных констант. Мы разработали инновационную многоуровневую структуру данных bitset, вдохновленную многоуровневыми таблицами страниц в памяти. Этот дизайн оптимизирует использование кэша CPU, что приводит к значительному улучшению производительности чтения и записи.
Sparse Track
Сравнение нашего решения для Sparse track (zilliz) с официальным базовым решением (linscan), победителем трека (pyanns) и решением Pinecone (pinecone_smips). При 90% recall наша пропускная способность составляет около 8 200 QPS, что в 82 раза выше базового решения с примерно 100 QPS, а также превосходит как победителя трека с 6 000 QPS, так и решение Pinecone с 7 400 QPS.
В этом треке наше решение основано на синергии графовых алгоритмов и оптимизаций, обусловленных разреженными векторами. Каждый разреженный вектор представлен как список кортежей (data[float32], index[int32]). Мы вводим многоточечное квантование для обработки данных, ориентированное на вычисления во время графового поиска и последующего уточнения. Кроме того, мы оптимизируем пропускную способность памяти, представляя index с помощью int16.
Задача заключается в максимизации поиска по скалярному произведению. В вычислениях скалярного произведения их величины влияют на важность значений. Большие величины имеют большую значимость, тогда как меньшие менее важны. Используя это понимание, мы реализуем стратегию отсечения во время графового поиска, отбрасывая значения с меньшими абсолютными величинами. После графового поиска мы выполняем уточнение с использованием полных векторов. Экспериментальные результаты показывают, что мы можем отсекать более 80% данных в векторах запросов без значительного ущерба для recall.
Мы используем технологию SIMD для быстрого пересечения отсортированных списков с целью ускоренных вычислений, тем самым достигая высокоэффективных расчетов скалярных произведений разреженных векторов.
Streaming Track
Сравнение нашего решения для Streaming track (zilliz) с официальным базовым решением (diskann), победителем трека (puck) и решением Pinecone (pinecone). Наш алгоритм достигает recall 0,9982, превосходя победителя трека и решение Pinecone с recall 0,986 и 0,9975 соответственно.
Наше решение для streaming track основано на графовых алгоритмах и SQ-квантовании.
Мы реализуем стратегию ленивого удаления для операций удаления, помечая векторы для удаления без немедленного изменения структуры графа. Граф не перестраивается до тех пор, пока не накопится заданное количество операций удаления.
Мы квантуем векторы с различной точностью как для графового поиска, так и для уточнения. Сначала мы используем векторы с более низкой точностью для графового поиска. Однако из-за нашей стратегии ленивого удаления удаленные векторы могут появляться в результатах поиска. Поэтому мы используем стратегию постфильтрации для исключения этих удаленных векторов. Наконец, мы используем квантованные векторы с более высокой точностью для уточнения результатов.
Примечание: Хотя наше решение не является open-source, мы объяснили нашу методологию и выпустили бинарные файлы в BigANN's GitHub repo для широкой доступности и воспроизводимости.
Алгоритмы BigANN будут интегрированы в продукты Zilliz
По мере развития AI векторный поиск стал необходимым для поддержки сложных производственных сценариев. Охват BigANN множества сценариев добавляет значительную практическую ценность. Мы рады активно участвовать в этом соревновании BigANN и с удовольствием решаем эти сложные алгоритмические задачи. Мы внедрим идеи, полученные в ходе этого процесса, в наши продукты, расширяя их влияние на более широкий круг задач.
Присоединяйтесь к нам!
В Zilliz мы стремимся создать лучшую в мире векторную базу данных, используя векторный поиск для решения реальных задач. Мы также постоянно исследуем сложные сценарии использования, вдохновленные BigANN и не только. Мы приглашаем единомышленников, интересующихся векторным поиском, системами баз данных или AI-технологиями, присоединиться к нам на этом пути. Если вам интересно, свяжитесь с нами! Узнайте больше о возможностях на нашей странице career и подайте заявку.
Этот пост написан Li Liu и Zihao Wang.
Читать далее
VDBBench Adds Cost-Aware Benchmarking for Vector Databases
Compare Zilliz Cloud, Pinecone, and turbopuffer with VDBBench cost-aware vector database benchmarks across latency, freshness, multitenancy, and cold starts.
Introducing Loon: A New Storage Engine for Vector Data That Never Stops Changing
Loon is a new storage engine for Milvus 3.0 and Zilliz Vector Lakebase, built to manage evolving vector datasets with ColumnGroups, row ID alignment, and Manifests.
Introducing Business Critical Plan: Enterprise-Grade Security and Compliance for Mission-Critical AI Applications
Discover Zilliz Cloud’s Business Critical Plan—offering advanced security, compliance, and uptime for mission-critical AI and vector database workloads.