An experimental study of context-free path query evaluation methods

Jochem Kuijpers, George Fletcher, Nikolay Yakovets, Tobias Lindaaker

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

Abstract

Context-free path queries extend regular path queries for increased expressiveness. A context-free grammar is used to recognize accepted paths by their label strings, or traces. Such queries arise naturally in graph analytics, e.g., in bioinformatics applications. Currently, the practical performance of methods for context-free path query evaluation is not well understood. In this work, we study three state of the art context-free path query evaluation methods. We measure the performance of these methods on diverse query workloads on various data sets and compare their results. We showcase how these evaluation methods scale as graphs get bigger and queries become larger or more ambiguous. We conclude that state of the art solutions are not able to cope with large graphs as found in practice.

LanguageEnglish
Title of host publicationProceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019
EditorsIvo Jimenez, Carlos Maltzahn, Tanu Malik
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages121-132
Number of pages12
ISBN (Electronic)9781450362160
DOIs
StatePublished - 23 Jul 2019
Event31st International Conference on Scientific and Statistical Database Management, SSDBM 2019 - Santa Cruz, United States
Duration: 23 Jul 201925 Jul 2019

Conference

Conference31st International Conference on Scientific and Statistical Database Management, SSDBM 2019
CountryUnited States
CitySanta Cruz
Period23/07/1925/07/19

Fingerprint

Context free grammars
Bioinformatics
Labels

Cite this

Kuijpers, J., Fletcher, G., Yakovets, N., & Lindaaker, T. (2019). An experimental study of context-free path query evaluation methods. In I. Jimenez, C. Maltzahn, & T. Malik (Eds.), Proceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019 (pp. 121-132). New York: Association for Computing Machinery, Inc. DOI: 10.1145/3335783.3335791
Kuijpers, Jochem ; Fletcher, George ; Yakovets, Nikolay ; Lindaaker, Tobias. / An experimental study of context-free path query evaluation methods. Proceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019. editor / Ivo Jimenez ; Carlos Maltzahn ; Tanu Malik. New York : Association for Computing Machinery, Inc, 2019. pp. 121-132
@inproceedings{cacd6dbe938c4408b6f376730d0f07e0,
title = "An experimental study of context-free path query evaluation methods",
abstract = "Context-free path queries extend regular path queries for increased expressiveness. A context-free grammar is used to recognize accepted paths by their label strings, or traces. Such queries arise naturally in graph analytics, e.g., in bioinformatics applications. Currently, the practical performance of methods for context-free path query evaluation is not well understood. In this work, we study three state of the art context-free path query evaluation methods. We measure the performance of these methods on diverse query workloads on various data sets and compare their results. We showcase how these evaluation methods scale as graphs get bigger and queries become larger or more ambiguous. We conclude that state of the art solutions are not able to cope with large graphs as found in practice.",
author = "Jochem Kuijpers and George Fletcher and Nikolay Yakovets and Tobias Lindaaker",
year = "2019",
month = "7",
day = "23",
doi = "10.1145/3335783.3335791",
language = "English",
pages = "121--132",
editor = "Ivo Jimenez and Carlos Maltzahn and Tanu Malik",
booktitle = "Proceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019",
publisher = "Association for Computing Machinery, Inc",
address = "United States",

}

Kuijpers, J, Fletcher, G, Yakovets, N & Lindaaker, T 2019, An experimental study of context-free path query evaluation methods. in I Jimenez, C Maltzahn & T Malik (eds), Proceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019. Association for Computing Machinery, Inc, New York, pp. 121-132, 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019, Santa Cruz, United States, 23/07/19. DOI: 10.1145/3335783.3335791

An experimental study of context-free path query evaluation methods. / Kuijpers, Jochem; Fletcher, George; Yakovets, Nikolay; Lindaaker, Tobias.

Proceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019. ed. / Ivo Jimenez; Carlos Maltzahn; Tanu Malik. New York : Association for Computing Machinery, Inc, 2019. p. 121-132.

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

TY - GEN

T1 - An experimental study of context-free path query evaluation methods

AU - Kuijpers,Jochem

AU - Fletcher,George

AU - Yakovets,Nikolay

AU - Lindaaker,Tobias

PY - 2019/7/23

Y1 - 2019/7/23

N2 - Context-free path queries extend regular path queries for increased expressiveness. A context-free grammar is used to recognize accepted paths by their label strings, or traces. Such queries arise naturally in graph analytics, e.g., in bioinformatics applications. Currently, the practical performance of methods for context-free path query evaluation is not well understood. In this work, we study three state of the art context-free path query evaluation methods. We measure the performance of these methods on diverse query workloads on various data sets and compare their results. We showcase how these evaluation methods scale as graphs get bigger and queries become larger or more ambiguous. We conclude that state of the art solutions are not able to cope with large graphs as found in practice.

AB - Context-free path queries extend regular path queries for increased expressiveness. A context-free grammar is used to recognize accepted paths by their label strings, or traces. Such queries arise naturally in graph analytics, e.g., in bioinformatics applications. Currently, the practical performance of methods for context-free path query evaluation is not well understood. In this work, we study three state of the art context-free path query evaluation methods. We measure the performance of these methods on diverse query workloads on various data sets and compare their results. We showcase how these evaluation methods scale as graphs get bigger and queries become larger or more ambiguous. We conclude that state of the art solutions are not able to cope with large graphs as found in practice.

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

U2 - 10.1145/3335783.3335791

DO - 10.1145/3335783.3335791

M3 - Conference contribution

SP - 121

EP - 132

BT - Proceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019

PB - Association for Computing Machinery, Inc

CY - New York

ER -

Kuijpers J, Fletcher G, Yakovets N, Lindaaker T. An experimental study of context-free path query evaluation methods. In Jimenez I, Maltzahn C, Malik T, editors, Proceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019. New York: Association for Computing Machinery, Inc. 2019. p. 121-132. Available from, DOI: 10.1145/3335783.3335791