Paper Info
Title
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching
Abstract
Despite the crucial role of cardinality estimation in query optimization, there has been no systematic and in-depth study of the existing cardinality estimation techniques for subgraph matching queries. In this paper, for the first time, we present a comprehensive study of the existing cardinality estimation techniques for subgraph matching queries, scaling far beyond the original experiments. We first introduce a novel framework called g-care that enables us to realize all existing techniques on top of it and that provides insights on their performance. By using g-care, we then reimplement representative cardinality estimation techniques for graph databases as well as relational databases. We next evaluate these techniques w.r.t accuracy on rdf and non-rdf graphs from different domains with subgraph matching queries of various topologies so far considered. Surprisingly, our results reveal that all existing techniques have serious problems in accuracy for various scenarios and datasets. Intriguingly, a simple sampling method based on an online aggregation technique designed for relational data, consistently outperforms all existing techniques.
Year
DOI
Venue
2020
10.1145/3318464.3389702
SIGMOD/PODS '20: International Conference on Management of Data Portland OR USA June, 2020
DocType
ISBN
Citations 
Conference
978-1-4503-6735-6
1
PageRank 
References 
Authors
0.35
0
6
Name
Order
Citations
PageRank
Yeonsu Park110.35
Seongyun Ko2241.66
Sourav S. Bhowmick31519272.35
Kyoungmin Kim462.10
Kijae Hong510.35
Wook-Shin Han680557.85