🚀 Попробуйте Zilliz Cloud, полностью управляемый Milvus, бесплатно — ощутите 10-кратное увеличение производительности! Попробовать сейчас>

milvus-logo
LFAI
  • Home
  • Blog
  • Ускорение поиска по сходству в действительно больших данных с помощью векторного индексирования

Ускорение поиска по сходству в действительно больших данных с помощью векторного индексирования

  • Engineering
December 05, 2019
milvus

Векторные системы поиска сходства - от компьютерного зрения до поиска новых лекарств - используются во многих популярных приложениях искусственного интеллекта (ИИ). Огромным компонентом, позволяющим эффективно запрашивать миллионные, миллиардные и даже триллионные наборы векторных данных, на которые опираются системы поиска сходства, является индексирование - процесс организации данных, который значительно ускоряет поиск в больших данных. В этой статье рассказывается о роли индексации в обеспечении эффективности поиска по векторному сходству, о различных типах индексов векторных инвертированных файлов (IVF) и о том, какой индекс следует использовать в различных сценариях.

Перейти к:

Как векторное индексирование ускоряет поиск по сходству и машинное обучение?

Системы поиска по сходству работают, сравнивая входные данные с базой данных, чтобы найти объекты, которые наиболее похожи на входные данные. Индексирование - это процесс эффективной организации данных, и оно играет важную роль в обеспечении полезности поиска по сходству, значительно ускоряя трудоемкие запросы к большим массивам данных. После индексации огромного набора векторных данных запросы могут быть направлены в кластеры или подмножества данных, которые с наибольшей вероятностью содержат векторы, похожие на входной запрос. На практике это означает, что для ускорения запросов к действительно большим векторным данным приходится жертвовать определенной степенью точности.

Можно провести аналогию со словарем, в котором слова отсортированы по алфавиту. При поиске слова можно быстро перейти к разделу, содержащему только слова с тем же начальным значением, что значительно ускоряет поиск определения вводимого слова.

Какие существуют типы индексов ЭКО и для каких сценариев они лучше всего подходят?

Существует множество индексов, предназначенных для поиска векторного сходства в высоких измерениях, и каждый из них имеет свои компромиссы в производительности, точности и требованиях к хранению данных. В этой статье рассматриваются несколько распространенных типов индексов ЭКО, их сильные и слабые стороны, а также результаты тестирования производительности для каждого типа индексов. В ходе тестирования производительности были определены время выполнения запроса и скорость запоминания для каждого типа индексов в Milvus, платформе управления векторными данными с открытым исходным кодом. Дополнительную информацию о среде тестирования см. в разделе "Методология" в нижней части этой статьи.

FLAT: Хорошо подходит для поиска в относительно небольших (миллионных) наборах данных, когда требуется 100-процентный отзыв.

Для приложений поиска векторного сходства, требующих идеальной точности и зависящих от относительно небольших (миллионных) наборов данных, индекс FLAT является хорошим выбором. FLAT не сжимает векторы и является единственным индексом, который может гарантировать точные результаты поиска. Результаты, полученные с помощью FLAT, можно также использовать для сравнения с результатами, полученными с помощью других индексов, которые имеют менее чем 100-процентный отзыв.

Точность FLAT обусловлена тем, что он использует исчерпывающий подход к поиску, то есть для каждого запроса целевой входной сигнал сравнивается с каждым вектором в наборе данных. Это делает FLAT самым медленным индексом в нашем списке и плохо подходит для запросов к массивным векторным данным. В Milvus нет параметров для индекса FLAT, и его использование не требует подготовки данных или дополнительного хранения.

Результаты тестирования производительности FLAT:

Тестирование времени выполнения запросов FLAT в Milvus проводилось на наборе данных, состоящем из 2 миллионов 128-мерных векторов.

Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_2.png Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_2.png

Основные выводы:

  • С увеличением nq (количества целевых векторов для запроса) время выполнения запроса увеличивается.
  • Используя индекс FLAT в Milvus, мы видим, что время запроса резко возрастает, когда nq превышает 200.
  • В целом, индекс FLAT быстрее и стабильнее при работе Milvus на GPU по сравнению с CPU. Однако запросы FLAT на CPU выполняются быстрее, когда nq меньше 20.

IVF_FLAT: Повышает скорость за счет точности (и наоборот).

Распространенным способом ускорения процесса поиска сходства за счет снижения точности является приближенный поиск ближайших соседей (ANN). Алгоритмы ANN снижают требования к хранению и вычислительную нагрузку, объединяя похожие векторы в кластеры, что приводит к ускорению поиска векторов. IVF_FLAT - это самый базовый тип инвертированного файлового индекса, в котором используется одна из форм поиска ANN.

IVF_FLAT делит векторные данные на некоторое количество кластеров (nlist), а затем сравнивает расстояния между целевым входным вектором и центром каждого кластера. В зависимости от количества кластеров, к которым система настроена на запрос (nprobe), результаты поиска сходства возвращаются на основе сравнений между целевым входным вектором и векторами только в наиболее похожих кластерах, что значительно сокращает время запроса.

Настраивая nprobe, можно найти идеальный баланс между точностью и скоростью для конкретного сценария. Результаты тестирования производительности IVF_FLAT показывают, что время выполнения запроса резко возрастает при увеличении как количества векторов целевого ввода (nq), так и количества кластеров для поиска (nprobe). IVF_FLAT не сжимает векторные данные, однако индексные файлы содержат метаданные, которые незначительно увеличивают требования к хранению по сравнению с исходным неиндексированным набором векторных данных.

Результаты тестирования производительности IVF_FLAT:

Тестирование времени выполнения запроса IVF_FLAT проводилось в Milvus с использованием публичного набора данных 1B SIFT, который содержит 1 миллиард 128-мерных векторов.

Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_3.png Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_3.png

Основные выводы:

  • При работе на CPU время запроса для индекса IVF_FLAT в Milvus увеличивается с ростом nprobe и nq. Это означает, что чем больше входных векторов содержит запрос или чем больше кластеров просматривает запрос, тем больше будет время выполнения запроса.
  • На GPU индекс показывает меньшую зависимость времени от изменений nq и nprobe. Это объясняется тем, что данные индекса велики, а копирование данных из памяти CPU в память GPU составляет большую часть общего времени выполнения запроса.
  • Во всех сценариях, кроме nq = 1 000 и nprobe = 32, индекс IVF_FLAT более эффективен при работе на CPU.

Тестирование производительности отзыва IVF_FLAT проводилось в Milvus с использованием как публичного набора данных 1M SIFT, содержащего 1 миллион 128-мерных векторов, так и набора данных glove-200-angular, содержащего более 1 миллиона 200-мерных векторов, для построения индекса (nlist = 16 384).

Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_4.png Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_4.png

Основные выводы:

  • Индекс IVF_FLAT можно оптимизировать по точности, добившись показателя recall выше 0,99 на наборе данных 1M SIFT при nprobe = 256.

IVF_SQ8: быстрее и менее требователен к ресурсам, чем IVF_FLAT, но также менее точен.

IVF_FLAT не производит никакого сжатия, поэтому индексные файлы, которые он создает, примерно такого же размера, как и исходные, необработанные векторные данные без индексации. Например, если исходный набор данных 1B SIFT имеет размер 476 ГБ, то индексные файлы IVF_FLAT будут немного больше (~470 ГБ). Загрузка всех индексных файлов в память займет 470 ГБ.

Если ресурсы памяти диска, CPU или GPU ограничены, IVF_SQ8 будет лучшим вариантом, чем IVF_FLAT. Этот тип индекса может преобразовать каждое FLOAT (4 байта) в UINT8 (1 байт), выполнив скалярное квантование. Это позволяет сократить потребление памяти на диске, CPU и GPU на 70-75 %. Для набора данных 1B SIFT индексные файлы IVF_SQ8 требуют всего 140 ГБ памяти.

Результаты тестирования производительности IVF_SQ8:

Тестирование времени выполнения запросов IVF_SQ8 проводилось в Milvus с использованием публичного набора данных 1B SIFT, содержащего 1 миллиард 128-мерных векторов, для построения индекса.

Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_5.png Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_5.png

Основные выводы:

  • За счет уменьшения размера индексного файла IVF_SQ8 обеспечивает заметный прирост производительности по сравнению с IVF_FLAT. Кривая производительности IVF_SQ8 похожа на кривую производительности IVF_FLAT, а время выполнения запроса увеличивается с ростом nq и nprobe.
  • Как и в случае с IVF_FLAT, производительность IVF_SQ8 выше при работе на CPU и при меньших значениях nq и nprobe.

Тестирование производительности IVF_SQ8 по отзывам проводилось в Milvus с использованием как публичного набора данных 1M SIFT, содержащего 1 миллион 128-мерных векторов, так и набора данных glove-200-angular, содержащего более 1 миллиона 200-мерных векторов, для построения индекса (nlist = 16 384).

Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_6.png Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_6.png

Основные выводы:

  • Несмотря на сжатие исходных данных, точность запросов в IVF_SQ8 существенно не снижается. При различных настройках nprobe показатель отзыва у IVF_SQ8 не более чем на 1 % ниже, чем у IVF_FLAT.

IVF_SQ8H: новый гибридный подход на GPU/CPU, который еще быстрее, чем IVF_SQ8.

IVF_SQ8H - это новый тип индекса, который улучшает производительность запросов по сравнению с IVF_SQ8. При запросе к индексу IVF_SQ8, работающему на CPU, большая часть общего времени запроса тратится на поиск nprobe кластеров, ближайших к целевому входному вектору. Чтобы сократить время запроса, IVF_SQ8 копирует данные для операций грубого квантования, которые меньше файлов индекса, в память GPU, что значительно ускоряет операции грубого квантования. Затем порог gpu_search_threshold определяет, на каком устройстве выполняется запрос. Если nq >= gpu_search_threshold, запрос выполняется на GPU; в противном случае запрос выполняется на CPU.

IVF_SQ8H - это гибридный тип индекса, требующий совместной работы CPU и GPU. Его можно использовать только с Milvus с поддержкой GPU.

Результаты тестирования производительности IVF_SQ8H:

Тестирование времени выполнения запроса IVF_SQ8H проводилось в Milvus с использованием публичного набора данных 1B SIFT, содержащего 1 миллиард 128-мерных векторов, для построения индекса.

Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_7.png Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_7.png

Основные выводы:

  • Когда nq меньше или равно 1000, время выполнения запросов в IVF_SQ8H почти в два раза быстрее, чем в IVFSQ8.
  • Когда nq = 2000, время выполнения запросов для IVFSQ8H и IVF_SQ8 одинаково. Однако если параметр gpu_search_threshold меньше 2000, IVF_SQ8H превосходит IVF_SQ8.
  • Показатель отзыва запросов у IVF_SQ8H идентичен показателю IVF_SQ8, что означает сокращение времени выполнения запросов без потери точности поиска.

Узнайте больше о Milvus, платформе для управления векторными данными в огромных масштабах.

Milvus - это платформа для управления векторными данными, которая позволяет использовать приложения для поиска по сходству в таких областях, как искусственный интеллект, глубокое обучение, традиционные векторные вычисления и т. д. Дополнительную информацию о Milvus можно найти на следующих ресурсах:

  • Milvus доступен под лицензией с открытым исходным кодом на GitHub.
  • В Milvus поддерживаются дополнительные типы индексов, включая индексы на основе графов и деревьев. Полный список поддерживаемых типов индексов можно найти в документации по векторным индексам в Milvus.
  • Чтобы узнать больше о компании, которая выпустила Milvus, посетите сайт Zilliz.com.
  • Пообщайтесь с сообществом Milvus или получите помощь в решении проблемы в Slack.

Методология

Среда тестирования производительности

В тестах производительности, о которых говорится в этой статье, использовалась следующая конфигурация сервера:

  • Intel ® Xeon ® Platinum 8163 @ 2,50 ГГц, 24 ядра
  • GeForce GTX 2080Ti x 4
  • 768 ГБ памяти

Соответствующие технические концепции

Хотя это и не обязательно для понимания данной статьи, здесь приведены несколько технических понятий, которые помогут интерпретировать результаты наших тестов производительности индекса:

Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_8.png Blog_Accelerating Similarity Search on Really Big Data with Vector Indexing_8.png

Ресурсы

Для написания этой статьи были использованы следующие источники:

    Try Managed Milvus for Free

    Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.

    Get Started

    Like the article? Spread the word

    Продолжить чтение