Evaluation of the context-free path querying algorithm based on matrix multiplication

Nikita Mishin, Iaroslav Sokolov, Egor Spirin, Vladimir Kutuev, Egor Nemchinov, Sergey Gorbatyuk, Semyon Grigorev

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

Recently proposed matrix multiplication based algorithm for context-free path querying (CFPQ) offloads the most performance-critical parts onto boolean matrices multiplication. Thus, it is possible to achieve high performance of CFPQ by means of modern parallel hardware and software. In this paper, we provide results of empirical performance comparison of different implementations of this algorithm on both real-world data and synthetic data for the worst cases.

Original languageEnglish
Title of host publicationProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
EditorsAkhil Arora, Arnab Bhattacharya, George Fletcher
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450367899
DOIs
StatePublished - 30 Jun 2019
Event2nd ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2019, co-located with the ACM SIGMOD International Conference on Management of Data 2019 - Amsterdam, Netherlands
Duration: 30 Jun 2019 → …

Conference

Conference2nd ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2019, co-located with the ACM SIGMOD International Conference on Management of Data 2019
CountryNetherlands
CityAmsterdam
Period30/06/19 → …

Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Keywords

  • Boolean matrix
  • Context-free grammar
  • Context-free path querying
  • CUDA
  • GPGPU
  • Graph databases
  • Matrix multiplication
  • Transitive closure

Fingerprint

Dive into the research topics of 'Evaluation of the context-free path querying algorithm based on matrix multiplication'. Together they form a unique fingerprint.

Cite this