Standard

Context-Free Path Querying by Kronecker Product. / Orachev, Egor; Epelbaum, Ilya; Azimov, Rustam; Grigorev, Semyon.

Advances in Databases and Information Systems - 24th European Conference, ADBIS 2020, Proceedings. ed. / Jérôme Darmont; Boris Novikov; Robert Wrembel. Springer Nature, 2020. p. 49-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12245 LNCS).

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

Harvard

Orachev, E, Epelbaum, I, Azimov, R & Grigorev, S 2020, Context-Free Path Querying by Kronecker Product. in J Darmont, B Novikov & R Wrembel (eds), Advances in Databases and Information Systems - 24th European Conference, ADBIS 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12245 LNCS, Springer Nature, pp. 49-59, 24th European Conference on Advances in Databases and Information Systems,ADBIS 2020, Lyon, France, 25/08/20. https://doi.org/10.1007/978-3-030-54832-2_6

APA

Orachev, E., Epelbaum, I., Azimov, R., & Grigorev, S. (2020). Context-Free Path Querying by Kronecker Product. In J. Darmont, B. Novikov, & R. Wrembel (Eds.), Advances in Databases and Information Systems - 24th European Conference, ADBIS 2020, Proceedings (pp. 49-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12245 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-54832-2_6

Vancouver

Orachev E, Epelbaum I, Azimov R, Grigorev S. Context-Free Path Querying by Kronecker Product. In Darmont J, Novikov B, Wrembel R, editors, Advances in Databases and Information Systems - 24th European Conference, ADBIS 2020, Proceedings. Springer Nature. 2020. p. 49-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-54832-2_6

Author

Orachev, Egor ; Epelbaum, Ilya ; Azimov, Rustam ; Grigorev, Semyon. / Context-Free Path Querying by Kronecker Product. Advances in Databases and Information Systems - 24th European Conference, ADBIS 2020, Proceedings. editor / Jérôme Darmont ; Boris Novikov ; Robert Wrembel. Springer Nature, 2020. pp. 49-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{e7f6de9db0454449b4b9a42315932de9,
title = "Context-Free Path Querying by Kronecker Product",
abstract = "Context-free path queries (CFPQ) extend the regular path queries (RPQ) by allowing context-free grammars to be used as constraints for paths. Algorithms for CFPQ are actively developed, but J. Kuijpers et al. have recently concluded, that existing algorithms are not performant enough to be used in real-world applications. Thus the development of new algorithms for CFPQ is justified. In this paper, we provide a new CFPQ algorithm which is based on such linear algebra operations as Kronecker product and transitive closure and handles grammars presented as recursive state machines. Thus, the proposed algorithm can be implemented by using high-performance libraries and modern parallel hardware. Moreover, it avoids grammar growth which provides the possibility for queries optimization.",
keywords = "CFPQ, Context-free grammars, Context-free path querying, Graph database, Kronecker product, Recursive state machines",
author = "Egor Orachev and Ilya Epelbaum and Rustam Azimov and Semyon Grigorev",
note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 24th European Conference on Advances in Databases and Information Systems,ADBIS 2020 ; Conference date: 25-08-2020 Through 27-08-2020",
year = "2020",
month = aug,
doi = "10.1007/978-3-030-54832-2_6",
language = "English",
isbn = "9783030548315",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "49--59",
editor = "J{\'e}r{\^o}me Darmont and Boris Novikov and Robert Wrembel",
booktitle = "Advances in Databases and Information Systems - 24th European Conference, ADBIS 2020, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - Context-Free Path Querying by Kronecker Product

AU - Orachev, Egor

AU - Epelbaum, Ilya

AU - Azimov, Rustam

AU - Grigorev, Semyon

N1 - Publisher Copyright: © 2020, Springer Nature Switzerland AG.

PY - 2020/8

Y1 - 2020/8

N2 - Context-free path queries (CFPQ) extend the regular path queries (RPQ) by allowing context-free grammars to be used as constraints for paths. Algorithms for CFPQ are actively developed, but J. Kuijpers et al. have recently concluded, that existing algorithms are not performant enough to be used in real-world applications. Thus the development of new algorithms for CFPQ is justified. In this paper, we provide a new CFPQ algorithm which is based on such linear algebra operations as Kronecker product and transitive closure and handles grammars presented as recursive state machines. Thus, the proposed algorithm can be implemented by using high-performance libraries and modern parallel hardware. Moreover, it avoids grammar growth which provides the possibility for queries optimization.

AB - Context-free path queries (CFPQ) extend the regular path queries (RPQ) by allowing context-free grammars to be used as constraints for paths. Algorithms for CFPQ are actively developed, but J. Kuijpers et al. have recently concluded, that existing algorithms are not performant enough to be used in real-world applications. Thus the development of new algorithms for CFPQ is justified. In this paper, we provide a new CFPQ algorithm which is based on such linear algebra operations as Kronecker product and transitive closure and handles grammars presented as recursive state machines. Thus, the proposed algorithm can be implemented by using high-performance libraries and modern parallel hardware. Moreover, it avoids grammar growth which provides the possibility for queries optimization.

KW - CFPQ

KW - Context-free grammars

KW - Context-free path querying

KW - Graph database

KW - Kronecker product

KW - Recursive state machines

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

U2 - 10.1007/978-3-030-54832-2_6

DO - 10.1007/978-3-030-54832-2_6

M3 - Conference contribution

AN - SCOPUS:85090095406

SN - 9783030548315

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 59

BT - Advances in Databases and Information Systems - 24th European Conference, ADBIS 2020, Proceedings

A2 - Darmont, Jérôme

A2 - Novikov, Boris

A2 - Wrembel, Robert

PB - Springer Nature

T2 - 24th European Conference on Advances in Databases and Information Systems,ADBIS 2020

Y2 - 25 August 2020 through 27 August 2020

ER -

ID: 84890048