Ускорение поиска по сходству в действительно больших данных с помощью векторного индексирования
Векторные системы поиска сходства - от компьютерного зрения до поиска новых лекарств - используются во многих популярных приложениях искусственного интеллекта (ИИ). Огромным компонентом, позволяющим эффективно запрашивать миллионные, миллиардные и даже триллионные наборы векторных данных, на которые опираются системы поиска сходства, является индексирование - процесс организации данных, который значительно ускоряет поиск в больших данных. В этой статье рассказывается о роли индексации в обеспечении эффективности поиска по векторному сходству, о различных типах индексов векторных инвертированных файлов (IVF) и о том, какой индекс следует использовать в различных сценариях.
Перейти к:
- Ускорение поиска сходства в действительно больших данных с помощью векторного индексирования
- Как векторное индексирование ускоряет поиск по сходству и машинное обучение?
- Что такое различные типы ЭКО-индексов и для каких сценариев они лучше всего подходят?
- FLAT: Хорошо подходит для поиска в относительно небольших (миллионных) наборах данных, когда требуется 100-процентный отзыв.
- IVF_FLAT: Повышает скорость за счет точности (и наоборот).
- IVF_SQ8: быстрее и менее требователен к ресурсам, чем IVF_FLAT, но и менее точен.
- IVF_SQ8H: новый гибридный подход на базе GPU/CPU, который еще быстрее, чем IVF_SQ8.
- Узнайте больше о Milvus, платформе для управления векторными данными в огромных масштабах.
- Методология
Как векторное индексирование ускоряет поиск по сходству и машинное обучение?
Системы поиска по сходству работают, сравнивая входные данные с базой данных, чтобы найти объекты, которые наиболее похожи на входные данные. Индексирование - это процесс эффективной организации данных, и оно играет важную роль в обеспечении полезности поиска по сходству, значительно ускоряя трудоемкие запросы к большим массивам данных. После индексации огромного набора векторных данных запросы могут быть направлены в кластеры или подмножества данных, которые с наибольшей вероятностью содержат векторы, похожие на входной запрос. На практике это означает, что для ускорения запросов к действительно большим векторным данным приходится жертвовать определенной степенью точности.
Можно провести аналогию со словарем, в котором слова отсортированы по алфавиту. При поиске слова можно быстро перейти к разделу, содержащему только слова с тем же начальным значением, что значительно ускоряет поиск определения вводимого слова.
Какие существуют типы индексов ЭКО и для каких сценариев они лучше всего подходят?
Существует множество индексов, предназначенных для поиска векторного сходства в высоких измерениях, и каждый из них имеет свои компромиссы в производительности, точности и требованиях к хранению данных. В этой статье рассматриваются несколько распространенных типов индексов ЭКО, их сильные и слабые стороны, а также результаты тестирования производительности для каждого типа индексов. В ходе тестирования производительности были определены время выполнения запроса и скорость запоминания для каждого типа индексов в 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
Основные выводы:
- С увеличением 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
Основные выводы:
- При работе на 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
Основные выводы:
- Индекс 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
Основные выводы:
- За счет уменьшения размера индексного файла 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
Основные выводы:
- Несмотря на сжатие исходных данных, точность запросов в 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
Основные выводы:
- Когда 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
Ресурсы
Для написания этой статьи были использованы следующие источники:
- "Энциклопедия систем баз данных", Ling Liu и M. Tamer Özsu.
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word