TY - UNPB

T1 - One Algorithm to Evaluate Them All

T2 - Unified Linear Algebra Based Approach to Evaluate Both Regular and Context-Free Path Queries

AU - Shemetova, Ekaterina

AU - Azimov, Rustam

AU - Orachev, Egor

AU - Epelbaum, Ilya

AU - Grigorev, Semyon

PY - 2021/3/26

Y1 - 2021/3/26

N2 - The Kronecker product-based algorithm for context-free path querying (CFPQ) was proposed by Orachev et al. (2020). We reduce this algorithm to operations over Boolean matrices and extend it with the mechanism to extract all paths of interest. We also prove $O(n^3/\log{n})$ time complexity of the proposed algorithm, where n is a number of vertices of the input graph. Thus, we provide the alternative way to construct a slightly subcubic algorithm for CFPQ which is based on linear algebra and incremental transitive closure (a classic graph-theoretic problem), as opposed to the algorithm with the same complexity proposed by Chaudhuri (2008). Our evaluation shows that our algorithm is a good candidate to be the universal algorithm for both regular and context-free path querying.

AB - The Kronecker product-based algorithm for context-free path querying (CFPQ) was proposed by Orachev et al. (2020). We reduce this algorithm to operations over Boolean matrices and extend it with the mechanism to extract all paths of interest. We also prove $O(n^3/\log{n})$ time complexity of the proposed algorithm, where n is a number of vertices of the input graph. Thus, we provide the alternative way to construct a slightly subcubic algorithm for CFPQ which is based on linear algebra and incremental transitive closure (a classic graph-theoretic problem), as opposed to the algorithm with the same complexity proposed by Chaudhuri (2008). Our evaluation shows that our algorithm is a good candidate to be the universal algorithm for both regular and context-free path querying.

KW - cs.DB

KW - cs.PL

M3 - Preprint

BT - One Algorithm to Evaluate Them All

ER -