Context-Free Path Querying with Single-Path Semantics by Matrix Multiplication
| Autor: | Semyon V. Grigorev, Rustam Azimov, Arseniy Terekhov, Artyom Khoroshev |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Kronecker product
Theoretical computer science Graph database Computer science Transitive closure 010103 numerical & computational mathematics 02 engineering and technology computer.software_genre 01 natural sciences Matrix multiplication symbols.namesake Linear algebra Path (graph theory) 0202 electrical engineering electronic engineering information engineering symbols Graph (abstract data type) 020201 artificial intelligence & image processing Logical matrix 0101 mathematics computer |
| Zdroj: | GRADES-NDA@SIGMOD |
| Popis: | Context-Free Path Querying (CFPQ) allows one to use context-free grammars as path constraints in navigational graph queries. Many algorithms for CFPQ were proposed but recently showed that the state-of-the-art CFPQ algorithms are still not performant enough for practical use. One promising way to achieve high-performance solutions for graph querying problems is to reduce them to linear algebra operations. Recently, there are two CFPQ solutions formulated in terms of linear algebra: the one based on the Boolean matrix multiplication operation proposed by Azimov et al. (2018) and the Kronecker product-based CFPQ algorithm proposed by Orachev et al. (2020). However, the algorithm based on matrix multiplication still does not support the most expressive all-path query semantics and cannot be truly compared with Kronecker product-based CFPQ algorithm. In this work, we introduce a new matrix-based CFPQ algorithm with all-path query semantics that allows us to extract all found paths for each pair of vertices. Also, we implement our algorithm by using appropriate high-performance libraries for linear algebra. Finally, we provide a comparison of the most performant linear algebra-based CFPQ algorithms for different query semantics. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|