Бумажное чтение|HM-ANN Когда ANNS встречается с гетерогенной памятью
HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogeneous Memory - это научная работа, принятая на конференции 2020 Conference on Neural Information Processing Systems(NeurIPS 2020). В данной работе предлагается новый алгоритм поиска сходства на основе графов, названный HM-ANN. Этот алгоритм учитывает как неоднородность памяти, так и неоднородность данных в современных аппаратных условиях. HM-ANN позволяет выполнять поиск сходства в миллиардных масштабах на одной машине без использования технологий сжатия. Гетерогенная память (HM) представляет собой комбинацию быстрой, но небольшой динамической памяти с произвольным доступом (DRAM) и медленной, но большой постоянной памяти (PMem). HM-ANN обеспечивает низкую задержку поиска и высокую точность поиска, особенно когда набор данных не помещается в DRAM. Алгоритм имеет явное преимущество перед современными решениями по поиску приближенных ближайших соседей (ANN).
С момента своего появления алгоритмы поиска на основе ANN ставили перед собой фундаментальную проблему компромисса между точностью запроса и его задержкой из-за ограниченной емкости DRAM. Чтобы хранить индексы в DRAM для быстрого доступа к запросам, необходимо ограничить количество точек данных или хранить сжатые векторы, что снижает точность поиска. Индексы на основе графиков (например, Hierarchical Navigable Small World, HNSW) имеют более высокую производительность во время выполнения запросов и точность поиска. Однако при работе с миллиардными массивами данных эти индексы могут потреблять DRAM на уровне 1 Тбайт.
Существуют и другие обходные пути, позволяющие не хранить в DRAM наборы данных миллиардного масштаба в необработанном виде. Когда набор данных слишком велик, чтобы поместиться в память на одной машине, используются сжатые подходы, такие как квантование произведения точек набора данных. Но запоминаемость этих индексов со сжатым набором данных обычно низкая из-за потери точности при квантовании. Субраманья и др. [1] исследуют использование твердотельных накопителей (SSD) для достижения миллиардных масштабов поиска ANN на одной машине с помощью подхода, названного Disk-ANN, где исходный набор данных хранится на SSD, а сжатое представление - в DRAM.
1.png
Гетерогенная память (HM) представляет собой комбинацию быстрой, но маленькой DRAM и медленной, но большой PMem. DRAM - это обычное оборудование, которое можно найти в каждом современном сервере, и доступ к нему относительно быстрый. Новые технологии PMem, такие как модули постоянной памяти Intel® Optane™ DC, устраняют разрыв между флэш-памятью на основе NAND (SSD) и DRAM, ликвидируя узкое место ввода-вывода. PMem долговечна, как SSD, и напрямую адресуется процессором, как память. Ренен и другие [2] обнаружили, что пропускная способность PMem при чтении на 2,6× ниже, а при записи на 7,5× ниже, чем у DRAM в настроенной экспериментальной среде.
HM-ANN - это точный и быстрый алгоритм поиска АНН с миллиардным масштабом, который работает на одной машине без сжатия. Дизайн HM-ANN обобщает идею HNSW, иерархическая структура которого естественным образом вписывается в HM. HNSW состоит из нескольких слоев - только слой 0 содержит весь набор данных, а все остальные слои содержат подмножество элементов из слоя, расположенного непосредственно под ним.
2.png
- Элементы в верхних слоях, которые включают только подмножества набора данных, занимают небольшую часть всего хранилища. Это обстоятельство делает их достойными кандидатами на размещение в DRAM. Таким образом, ожидается, что большинство поисков в HM-ANN будет происходить в верхних слоях, что позволяет максимально использовать характеристики быстрого доступа DRAM. Однако в случае HNSW большинство поисков происходит в нижнем слое.
- Самый нижний слой содержит весь набор данных, что делает его подходящим для размещения в PMem. Поскольку доступ к слою 0 происходит медленнее, предпочтительнее, чтобы каждый запрос обращался только к небольшой его части, а частота доступа была снижена.
Алгоритм построения графа
3.png
Ключевая идея построения HM-ANN заключается в создании высококачественных верхних слоев, чтобы обеспечить лучшую навигацию для поиска на уровне 0. Таким образом, большая часть доступа к памяти происходит в DRAM, а доступ в PMem сокращается. Чтобы сделать это возможным, алгоритм построения HM-ANN имеет нисходящую фазу вставки и восходящую фазу продвижения.
Фаза вставки сверху вниз строит навигационный граф малого мира по мере размещения самого нижнего слоя на PMem.
Фаза продвижения снизу вверх продвигает поворотные точки из нижнего слоя для формирования верхних слоев, которые размещаются на DRAM без потери точности. Если в слое 1 создана высококачественная проекция элементов из слоя 0, поиск в слое 0 находит точных ближайших соседей запроса всего за несколько переходов.
- Вместо использования случайного выбора в HNSW для продвижения, HM-ANN использует стратегию продвижения с высокой степенью, чтобы продвигать элементы с наивысшей степенью в слое 0 в слой 1. Для более высоких слоев HM-ANN продвигает узлы с высокой степенью в верхний слой на основе коэффициента продвижения.
- HM-ANN продвигает больше узлов из слоя 0 в слой 1 и устанавливает большее максимальное количество соседей для каждого элемента в слое 1. Количество узлов в верхних слоях определяется доступным пространством DRAM. Поскольку слой 0 не хранится в DRAM, повышение плотности хранения каждого слоя в DRAM повышает качество поиска.
Алгоритм поиска графов
4.png
Алгоритм поиска состоит из двух фаз: быстрого поиска в памяти и параллельного поиска на слое 0 с предварительной выборкой.
Быстрый поиск в памяти
Как и в HNSW, поиск в DRAM начинается с точки входа в самом верхнем слое, а затем выполняется 1 жадный поиск от вершины до второго слоя. Чтобы сузить пространство поиска в слое 0, HM-ANN выполняет поиск в слое 1 с бюджетом поиска efSearchL1
, который ограничивает размер списка кандидатов в слое 1. Эти кандидаты из списка используются в качестве нескольких точек входа для поиска в слое 0, чтобы повысить качество поиска в слое 0. В то время как HNSW использует только одну точку входа, разрыв между слоем 0 и слоем 1 обрабатывается в HM-ANN более специально, чем разрывы между любыми другими двумя слоями.
Параллельный поиск в слое 0 с предварительной выборкой
В нижнем слое HM-ANN равномерно разделяет вышеупомянутые кандидаты из поиска слоя 1 и рассматривает их как точки входа для выполнения параллельного многозадачного 1-жадного поиска с потоками. Лучшие кандидаты из каждого поиска собираются, чтобы найти лучших кандидатов. Как известно, спуск с уровня 1 на уровень 0 в точности соответствует переходу на PMem. Параллельный поиск скрывает задержку PMem и наилучшим образом использует пропускную способность памяти, чтобы улучшить качество поиска без увеличения времени поиска.
HM-ANN реализует программно-управляемый буфер в DRAM для предварительной выборки данных из PMem перед обращением к памяти. При поиске на уровне 1 HM-ANN асинхронно копирует соседние элементы кандидатов в efSearchL1
и связи соседних элементов на уровне 1 из PMem в буфер. Когда происходит поиск в слое 0, часть данных, к которым нужно получить доступ, уже предварительно сгенерирована в DRAM, что скрывает задержку доступа к PMem и приводит к сокращению времени запроса. Это соответствует цели проектирования HM-ANN, где большинство обращений к памяти происходит в DRAM, а обращения к памяти PMem сокращаются.
В данной работе проведена обширная оценка. Все эксперименты проводятся на машине с процессором Intel Xeon Gold 6252 CPU@2.3GHz. В качестве быстрой памяти используется DDR4 (96 ГБ), а в качестве медленной - Optane DC PMM (1,5 ТБ). Оцениваются пять наборов данных: BIGANN, DEEP1B, SIFT1M, DEEP1M и GIST1M. Для тестирования миллиардных масштабов используются следующие схемы: методы, основанные на квантовании (IMI+OPQ и L&C), методы, основанные на некомпрессии (HNSW и NSG).
Сравнение алгоритмов миллиардного масштаба
5.png
В таблице 1 приведено сравнение времени построения и хранения различных индексов на основе графов. Наименьшее время построения занимает HNSW, а HM-ANN требуется на 8 % больше времени, чем HNSW. С точки зрения использования всего хранилища, индексы HM-ANN на 5-13 % больше, чем HSNW, поскольку они перемещают больше узлов из слоя 0 в слой 1.
6.png
На рисунке 1 проанализирована производительность запросов с использованием различных индексов. На рисунках 1 (a) и (b) показано, что HM-ANN достигает показателя top-1 recall > 95 % за 1 мс. На рисунках 1 © и (d) показано, что HM-ANN достигает топ-100 запросов на уровне > 90 % за 4 мс. HM-ANN обеспечивает наилучшую производительность по соотношению "задержка - запоминание" по сравнению со всеми остальными подходами.
Сравнение алгоритмов миллионного масштаба
7.png
На рисунке 2 показана производительность запросов различных индексов в условиях чистой DRAM. HNSW, NSG и HM-ANN оцениваются на трех миллионных наборах данных, помещающихся в DRAM. HM-ANN по-прежнему демонстрирует лучшую производительность запросов, чем HNSW. Причина в том, что общее количество вычислений расстояния в HM-ANN меньше (в среднем 850/запрос), чем в HNSW (в среднем 900/запрос), чтобы достичь 99 % запоминания.
8.png
Эффективность продвижения по высоким степеням
На рисунке 3 сравниваются стратегии случайного продвижения и продвижения с высокой степенью в одной и той же конфигурации. Стратегия продвижения с высокой степенью превосходит базовую. Стратегия продвижения по высокой степени работает в 1,8 раза, 4,3 раза и 3,9 раза быстрее, чем случайное продвижение, для достижения целей 95 %, 99 % и 99,5 % отзыва соответственно.
10.png
Эффективность методов управления памятью
На рисунке 5 приведена серия шагов между HNSW и HM-ANN, чтобы показать, как каждая оптимизация HM-ANN способствует улучшению производительности. BP означает продвижение снизу вверх при построении индекса. PL0 означает параллельный поиск на уровне 0, а DP - предварительную выборку данных из PMem в DRAM. Шаг за шагом производительность поиска HM-ANN увеличивается.
Новый алгоритм индексации и поиска на основе графов, названный HM-ANN, объединяет иерархическую конструкцию ИНС на основе графов с неоднородностью памяти в HM. Оценки показывают, что HM-ANN принадлежит к новым современным индексам в миллиардных наборах данных.
Мы заметили тенденцию в научных кругах, а также в промышленности, когда особое внимание уделяется созданию индексов на постоянных устройствах хранения данных. Чтобы разгрузить DRAM, Disk-ANN [1] - индекс, построенный на SSD, пропускная способность которого значительно ниже, чем у PMem. Однако построение HM-ANN по-прежнему занимает несколько дней, в чем нет большой разницы по сравнению с Disk-ANN. Мы считаем, что время сборки HM-ANN можно оптимизировать, если более тщательно использовать характеристики PMem, например, помнить о гранулярности PMem (256 байт) и использовать потоковые инструкции для обхода кэш-линий. Мы также считаем, что в будущем будет предложено больше подходов с использованием долговременных устройств хранения данных.
[1]: Suhas Jayaram Subramanya and Devvrit and Rohan Kadekodi and Ravishankar Krishaswamy and Ravishankar Krishaswamy: DiskANN: быстрый точный поиск ближайших соседей по миллиарду точек на одном узле, NIPS, 2019
DiskANN: быстрый точный поиск ближайших соседей по миллиардным точкам на одном узле
[2]: Александр ван Ренен и Лукас Фогель и Виктор Лейс и Томас Нойманн и Альфонс Кемпер: Примитивы ввода/вывода в постоянную память, CoRR & DaMoN, 2019
- Алгоритм построения графа
- Алгоритм поиска графов
- Сравнение алгоритмов миллиардного масштаба
- Сравнение алгоритмов миллионного масштаба
- Эффективность продвижения по высоким степеням
- Эффективность методов управления памятью
On This Page
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word