Исследовательская группа

Лаборатория языковых инструментов

Вычисление КС-запросов к графам с семантикой всех путей

November 30

На семинаре мы поговорим о матричном алгоритме вычисления КС-запросов к графам с all-path семантикой, которая требует вернуть все найденные пути, соответствующие запросу. Реализация данного алгоритма использует SuiteSparse — реализацию стандарта GraphBLAS, определяющего базовые блоки для формулирования графовых алгоритмов на языке линейной алгебры. Мы сравним полученную реализацию с аналогичной реализацией тензорного алгоритма для all-path семантики.

Докладчик: Рустам Азимов

Материалы

1) Аналогичный матричный CFPQ алгоритм с single-path семантикой: Terekhov A. et al. Context-Free Path Querying with Single-Path Semantics by Matrix Multiplication //Proceedings of the 3rd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). – 2020. – С. 1-12.

2) Тензорный CFPQ алгоритм: Orachev E. et al. Context-Free Path Querying by Kronecker Product //European Conference on Advances in Databases and Information Systems. – Springer, Cham, 2020. – С. 49-59.

Семинар пройдет онлайн 30 ноября в 17:30, ссылка Google meet: https://meet.google.com/myu-dhmz-gvu