Standard

Evaluation of the context-free path querying algorithm based on matrix multiplication. / Mishin, Nikita; Sokolov, Iaroslav; Spirin, Egor; Kutuev, Vladimir; Nemchinov, Egor; Gorbatyuk, Sergey; Grigorev, Semyon.

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ed. / Akhil Arora; Arnab Bhattacharya; George Fletcher. Association for Computing Machinery, 2019.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Mishin, N, Sokolov, I, Spirin, E, Kutuev, V, Nemchinov, E, Gorbatyuk, S & Grigorev, S 2019, Evaluation of the context-free path querying algorithm based on matrix multiplication. in A Arora, A Bhattacharya & G Fletcher (eds), Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Association for Computing Machinery, 2nd 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, 30/06/19. https://doi.org/10.1145/3327964.3328503

APA

Mishin, N., Sokolov, I., Spirin, E., Kutuev, V., Nemchinov, E., Gorbatyuk, S., & Grigorev, S. (2019). Evaluation of the context-free path querying algorithm based on matrix multiplication. In A. Arora, A. Bhattacharya, & G. Fletcher (Eds.), Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems Association for Computing Machinery. https://doi.org/10.1145/3327964.3328503

Vancouver

Mishin N, Sokolov I, Spirin E, Kutuev V, Nemchinov E, Gorbatyuk S et al. Evaluation of the context-free path querying algorithm based on matrix multiplication. In Arora A, Bhattacharya A, Fletcher G, editors, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Association for Computing Machinery. 2019 https://doi.org/10.1145/3327964.3328503

Author

Mishin, Nikita ; Sokolov, Iaroslav ; Spirin, Egor ; Kutuev, Vladimir ; Nemchinov, Egor ; Gorbatyuk, Sergey ; Grigorev, Semyon. / Evaluation of the context-free path querying algorithm based on matrix multiplication. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. editor / Akhil Arora ; Arnab Bhattacharya ; George Fletcher. Association for Computing Machinery, 2019.

BibTeX

@inproceedings{aa800a73fd714de88f3d9d9c37793e2b,
title = "Evaluation of the context-free path querying algorithm based on matrix multiplication",
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.",
keywords = "Boolean matrix, Context-free grammar, Context-free path querying, CUDA, GPGPU, Graph databases, Matrix multiplication, Transitive closure",
author = "Nikita Mishin and Iaroslav Sokolov and Egor Spirin and Vladimir Kutuev and Egor Nemchinov and Sergey Gorbatyuk and Semyon Grigorev",
year = "2019",
month = jun,
day = "30",
doi = "10.1145/3327964.3328503",
language = "English",
isbn = "9781450367899",
editor = "Akhil Arora and Arnab Bhattacharya and George Fletcher",
booktitle = "Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",
publisher = "Association for Computing Machinery",
address = "United States",
note = "2nd 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 ; Conference date: 30-06-2019",

}

RIS

TY - GEN

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

AU - Mishin, Nikita

AU - Sokolov, Iaroslav

AU - Spirin, Egor

AU - Kutuev, Vladimir

AU - Nemchinov, Egor

AU - Gorbatyuk, Sergey

AU - Grigorev, Semyon

PY - 2019/6/30

Y1 - 2019/6/30

N2 - 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.

AB - 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.

KW - Boolean matrix

KW - Context-free grammar

KW - Context-free path querying

KW - CUDA

KW - GPGPU

KW - Graph databases

KW - Matrix multiplication

KW - Transitive closure

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

UR - http://www.mendeley.com/research/evaluation-contextfree-path-querying-algorithm-based-matrix-multiplication

U2 - 10.1145/3327964.3328503

DO - 10.1145/3327964.3328503

M3 - Conference contribution

AN - SCOPUS:85074447325

SN - 9781450367899

BT - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

A2 - Arora, Akhil

A2 - Bhattacharya, Arnab

A2 - Fletcher, George

PB - Association for Computing Machinery

T2 - 2nd 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

Y2 - 30 June 2019

ER -

ID: 49739696