Path-centric Cardinality Estimation for Subgraph Matching

Summary: Introduces PathCE, a path-centric cardinality estimation framework that builds a compact path-centric summary graph (PSG) of short-path query statistics to decompose graph queries into sub-paths and produce upper-bound cardinality estimates. Includes PSGBuilder, a linear-time parallel PSG construction algorithm; empirically achieves substantially better accuracy, latency, and construction scalability than prior estimators. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13942
Venue: VLDB
Year: 2025
Pagerank: 4.2721228e-05
Overall Rank: 9,845 | 31.52%
DOI: 10.14778/3746405.3746428

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,308	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 32 of 32 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040449103
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
204	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034784455
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
629	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018942366
789	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016634256
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
1,193	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013414989
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011049779
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010922679
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,364	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	8.9554751e-05
2,505	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.634551e-05
2,762	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	8.1585394e-05
3,449	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	7.0824319e-05
3,511	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.0254052e-05
3,646	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8853079e-05
3,778	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7747398e-05
3,990	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5581983e-05
4,417	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	6.2037371e-05
4,523	Simplicity Done Right for Join Ordering	2021	CIDR	6.1135504e-05
4,543	FACE: A Normalizing Flow based Cardinality Estimator	2022	VLDB	6.1011198e-05
5,972	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD	5.2474768e-05
6,368	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB	5.0937722e-05
6,714	Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks	2024	SIGMOD	4.9512171e-05
9,788	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	4.2818172e-05
9,877	Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation	2025	VLDB	4.2656547e-05
9,878	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	4.2656547e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,281	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.128862e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
6,704	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	4.9554912e-05
3,646	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8853079e-05
6,289	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	5.1275309e-05
6,441	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0603113e-05
3,511	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.0254052e-05
1,775	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010602927
9,728	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	4.2942813e-05
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907