TY - GEN

T1 - Context-free path querying by matrix multiplication

AU - Azimov, Rustam

AU - Grigorev, Semyon

PY - 2018/6/10

Y1 - 2018/6/10

N2 - Context-free path querying is a technique, which recently gains popularity in many areas, for example, graph databases, bioinformatics, static analysis, etc. In some of these areas, it is often required to query large graphs, and existing algorithms demonstrate a poor performance in this case. The generalization of matrix-based Valiant's context-free language recognition algorithm for graph case is widely considered as a recipe for efficient context-free path querying; however, no progress has been made in this direction so far. We propose the first generalization of matrix-based Valiant's algorithm for context-free path querying. Our generalization does not deliver a truly sub-cubic worst-case complexity algorithm, whose existence still remains a hard open problem in the area. On the other hand, the utilization of matrix operations (such as matrix multiplication) in the process of context-free path query evaluation makes it possible to efficiently apply a wide class of optimizations and computing techniques, such as GPGPU (General-Purpose computing on Graphics Processing Units), parallel processing, sparse matrix representation, distributed-memory computation, etc. Indeed, the evaluation on a set of conventional benchmarks shows, that our algorithm outperforms the existing ones.

AB - Context-free path querying is a technique, which recently gains popularity in many areas, for example, graph databases, bioinformatics, static analysis, etc. In some of these areas, it is often required to query large graphs, and existing algorithms demonstrate a poor performance in this case. The generalization of matrix-based Valiant's context-free language recognition algorithm for graph case is widely considered as a recipe for efficient context-free path querying; however, no progress has been made in this direction so far. We propose the first generalization of matrix-based Valiant's algorithm for context-free path querying. Our generalization does not deliver a truly sub-cubic worst-case complexity algorithm, whose existence still remains a hard open problem in the area. On the other hand, the utilization of matrix operations (such as matrix multiplication) in the process of context-free path query evaluation makes it possible to efficiently apply a wide class of optimizations and computing techniques, such as GPGPU (General-Purpose computing on Graphics Processing Units), parallel processing, sparse matrix representation, distributed-memory computation, etc. Indeed, the evaluation on a set of conventional benchmarks shows, that our algorithm outperforms the existing ones.

KW - Context-free grammar

KW - Context-free path querying

KW - GPGPU

KW - Graph databases

KW - Matrix multiplication

KW - Transitive closure

UR - http://www.scopus.com/inward/record.url?scp=85050280638&partnerID=8YFLogxK

U2 - 10.1145/3210259.3210264

DO - 10.1145/3210259.3210264

M3 - Conference contribution

AN - SCOPUS:85050280638

T3 - Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018

BT - Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018

A2 - Bhattacharya, Arnab

A2 - Fletcher, George

A2 - Roy, Shourya

A2 - Arora, Akhil

A2 - Larriba Pey, Josep Lluis

A2 - West, Robert

PB - Association for Computing Machinery

T2 - 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2018

Y2 - 10 June 2018

ER -