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.
| Language | English |
|---|---|
| Title of host publication | Proceedings of the 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019 |
| Editors | Ivo Jimenez, Carlos Maltzahn, Tanu Malik |
| Place of Publication | New York |
| Publisher | Association for Computing Machinery, Inc |
| Pages | 121-132 |
| Number of pages | 12 |
| ISBN (Electronic) | 9781450362160 |
| DOIs | |
| State | Published - 23 Jul 2019 |
| Event | 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019 - Santa Cruz, United States Duration: 23 Jul 2019 → 25 Jul 2019 |
Conference
| Conference | 31st International Conference on Scientific and Statistical Database Management, SSDBM 2019 |
|---|---|
| Country | United States |
| City | Santa Cruz |
| Period | 23/07/19 → 25/07/19 |
Fingerprint
Cite this
}
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 proceeding › Conference contribution › Academic › peer-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 -