Path-centric Cardinality Estimation for Subgraph Matching

Download PDF

Abstract

This paper presents PathCE , a path-centric cardinality estimation framework for subgraph matching. PathCE improves estimation accuracy by utilizing statistics from short graph queries. At its core is a novel data structure called the path-centric summary graph ( PSG ), which captures short path query statistics from a data graph 𝐺 and represents them in a new graph G . Given a graph query 𝑄 and a PSG graph G for 𝐺 , PathCE decomposes 𝑄 into a simpler query Q , where each edge in Q corresponds to a sub-path query in 𝑄 with statistics included in G . PathCE estimates the cardinality using Q and G , requiring significantly fewer estimation iterations while ensuring that the estimate remains an upper bound on the true cardinality of 𝑄 ( 𝐺 ) . It also includes PSGBuilder , a parallelly scalable algorithm that constructs PSG ’s for any given graph in linear time, efficiently scaling with the number of processors. Empirical results on real-world and synthetic datasets show that PathCE outperforms state-of-the-art baselines in accuracy, estimation latency, and summary construction efficiency.