GraphZero
ACM SIGOPS Operating Systems Review · 02.06.2021 · 55 (1) · 21-37
DOI: 10.1145/3469379.3469383 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGOPS Operating Systems Review, online erschienen am 06.06.2021. Verfasst von Daniel Mawhirter und 4 weiteren Autor:innen. Die Arbeit wurde bisher 48-mal zitiert (Crossref) und nennt 62 Literaturangaben.
Abstract (Originalsprache)
Subgraph matching is a fundamental task in many applications which identifies all the embeddings of a query pattern in an input graph. Compilation-based subgraph matching systems generate specialized implementations for the provided patterns and often substantially outperform other systems. However, the generated code causes significant computation redundancy and the compilation process incurs too much overhead to be used online, both due to the inherent symmetry in the structure of the query pattern. In this paper, we propose an optimizing query compiler, named GraphZero, to completely address these limitations through symmetry breaking based on group theory. GraphZero implements three novel techniques. First, its schedule explorer efficiently prunes the schedule space without missing any high-performance schedule. Second, it automatically generates and enforces a set of restrictions to eliminate computation redundancy. Third, it generalizes orientation, a surprisingly effective optimization that was only used for clique patterns, to apply to arbitrary patterns. Evaluation on multiple query patterns shows that GraphZero outperforms two state-of-the-art compilation and non-compilation based systems by up to 40X and 2654X, respectively.
Zitieren
APA
Mawhirter, D., Reinehr, S., Holmes, C., Liu, T., & Wu, B. (2021). GraphZero. ACM SIGOPS Operating Systems Review, 55(1), 21-37. https://doi.org/10.1145/3469379.3469383
Vancouver
Mawhirter D, Reinehr S, Holmes C, Liu T, Wu B. GraphZero. ACM SIGOPS Operating Systems Review. 2021;55(1):21-37. doi:10.1145/3469379.3469383
BibTeX
@article{Mawhirter2021,
author = {Mawhirter, Daniel and Reinehr, Sam and Holmes, Connor and Liu, Tongping and Wu, Bo},
title = {GraphZero},
journal = {ACM SIGOPS Operating Systems Review},
year = {2021},
volume = {55},
number = {1},
pages = {21--37},
doi = {10.1145/3469379.3469383}
}
EUVIMED