Библиотека PAM - PAM library

PAM (параллельные расширенные карты) это параллельная библиотека C ++ с открытым исходным кодом, реализующая интерфейс для последовательности, заказанные наборы, заказал карты, и дополненные карты[1]. Библиотека доступна на GitHub. Он использует базовый сбалансированная двоичная древовидная структура с помощью основанные на соединениях алгоритмы [1]. PAM поддерживает четыре схемы балансировки, включая Деревья АВЛ, красно-черные деревья, Treaps и деревья со сбалансированным весом.

PAM - это параллельная библиотека, которая также безопасна для параллелизма. Его параллелизм может быть поддержан шелк, OpenMP или планировщик в PBBS[2]. Теоретически все алгоритмы в PAM работоспособны и имеют полилогарифмическую глубину. PAM использует базовый стойкий древовидная структура, позволяющая поддерживать несколько версий. PAM также поддерживает эффективный сборщик мусора.

Интерфейс

Последовательности

Чтобы определить последовательность, пользователям необходимо указать ключевой тип последовательности.

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

Заказанные наборы

Чтобы определить упорядоченный набор, пользователям необходимо указать тип ключа и функцию сравнения, определяющую общий заказ по типу ключа.

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

Заказанные карты

Чтобы определить упорядоченную карту, пользователям необходимо указать тип ключа, функцию сравнения по типу ключа и тип значения.

Помимо интерфейса упорядоченного набора, PAM также поддерживает функции для упорядоченных карт, такие как вставка с объединением значений.

Дополненные карты

Чтобы определить дополненная карта пользователям необходимо указать тип ключа, функцию сравнения по типу ключа, тип значения, тип расширенного значения, базовую функцию, функцию объединения и идентификатор функции объединения.

Помимо интерфейса упорядоченной карты, PAM также поддерживает функции для расширенных карт, такие как aug_range.

Помимо древовидной структуры, PAM также реализует структура префикса для дополненных карт.

Реализация для примеров приложений

Библиотека также предоставляет примеры реализаций для ряда приложений, в том числе одномерный ударный запрос (с использованием интервальные деревья, 2D запрос диапазона (с помощью дерево диапазона и алгоритм Sweepline ), Запрос сегмента 2D (с использованием дерево сегментов и алгоритм Sweepline ), Запрос 2D-прямоугольника (с использованием древовидной структуры и алгоритм Sweepline ), поиск по инвертированному индексу, так далее.

Используется в приложениях

Библиотека протестирована в различных приложениях, в том числе в тестах баз данных.[3], 2D дерево сегментов[4], 2D дерево интервалов[1], инвертированный индекс[1] и мультиверсионный контроль параллелизма[5].

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

  1. ^ а б c d Сунь, Ихан; Феризович, Даниэль; Беллок, Гай Э. (23 марта 2018 г.). «PAM: параллельные дополненные карты». Уведомления ACM SIGPLAN. 53 (1): 290–304. Дои:10.1145/3200691.3178509. ISSN  0362-1340. Получено 5 сентября 2020.
  2. ^ Библиотека набора тестов на основе проблем
  3. ^ Сунь, Ихан; Blelloch, Guy E .; Лим, Ван Шен; Павел, Андрей (1 октября 2019). «О поддержке эффективной изоляции моментальных снимков для гибридных рабочих нагрузок с многоверсионными индексами». Труды эндаумента VLDB. 13 (2): 211–225. Дои:10.14778/3364324.3364334. ISSN  2150-8097.
  4. ^ Сунь, Ихан; Блеллох, Гай Э. (1 января 2019 г.). «Запросы с параллельным диапазоном, сегментами и прямоугольниками с расширенными картами». Протоколы совещания по разработке алгоритмов и экспериментам (ALENEX) 2019 г.. Общество промышленной и прикладной математики: 159–173. Дои:10.1137/1.9781611975499.13.
  5. ^ Бен-Давид, Наама; Blelloch, Guy E .; Сунь, Ихан; Вэй, Юаньхао (17 июня 2019 г.). «Многоверсионный параллелизм с ограниченной задержкой и точной сборкой мусора». Материалы 31-го симпозиума ACM по параллелизму в алгоритмах и архитектурах. Ассоциация вычислительной техники: 241–252. Дои:10.1145/3323165.3323185.


внешние ссылки

  • PAM, параллельная расширенная библиотека карт.