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

PAM (Parallel Augmented Maps) — это параллельная библиотека C++ с открытым исходным кодом, реализующая интерфейс для последовательностей, упорядоченных наборов , упорядоченных карт и дополненных карт . ^[1] Библиотека доступна на GitHub. Он использует базовую сбалансированную структуру двоичного дерева с использованием алгоритмов на основе соединений . ^[1] PAM поддерживает четыре схемы балансировки, включая деревья AVL , красно-черные деревья , трепы и деревья с балансировкой веса .

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

Интерфейс

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

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

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

[pam-1] Jump up to: ^а ^б ^с ^д Сунь, Ихан; Феризович, Дэниел; Беллок, Гай Э. (23 марта 2018 г.). «ПАМ: параллельные дополненные карты» . Уведомления ACM SIGPLAN . 53 (1): 290–304. дои : 10.1145/3200691.3178509 . ISSN 0362-1340 . Проверено 5 сентября 2020 г.

[pbbs-2] Библиотека набора проблемно-ориентированных тестов

[db-3] Сунь, Ихан; Блеллок, Гай Э.; Лим, Ван Шен; Павел, Андрей (1 октября 2019 г.). «О поддержке эффективной изоляции моментальных снимков для гибридных рабочих нагрузок с многоверсионными индексами» . Труды Фонда VLDB . 13 (2): 211–225. дои : 10.14778/3364324.3364334 . ISSN 2150-8097 . S2CID 204841857 .

[geo-4] Сунь, Ихан; Белллох, Гай Э. (1 января 2019 г.). «Параллельные запросы диапазона, сегмента и прямоугольника с расширенными картами» . Материалы совещания по алгоритмической разработке и экспериментам (ALENEX) , 2019 г. Общество промышленной и прикладной математики: 159–173. arXiv : 1803.08621 . дои : 10.1137/1.9781611975499.13 . ISBN 978-1-61197-549-9 .

[concurrency-5] Бен-Давид, Наама; Блеллок, Гай Э.; Сунь, Ихан; Вэй, Юаньхао (17 июня 2019 г.). «Многоверсионный параллелизм с ограниченной задержкой и точным сбором мусора». 31-й симпозиум ACM по параллелизму в алгоритмах и архитектурах . Ассоциация вычислительной техники. стр. 241–252. дои : 10.1145/3323165.3323185 . ISBN 9781450361842 .

[1]

[2]

[3]

[4]

[5]