Extending Graph Patterns with Conditions

Summary: CGPs extend graph patterns with per-edge conditions, so edges exist only if the condition holds, enabling missing-link detection and richer dependencies in compact form. Complexity: linear-time for consistency; NP-complete for matching; NP^p-complete for incremental matching; Pi2-complete for containment; plus practical CGP/multi-CGP matching and incremental optimization with empirical validation on real and synthetic graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5798
Venue: SIGMOD
Year: 2020
Pagerank: 4.6902655e-05
Overall Rank: 7,641 | 46.85%
DOI: 10.1145/3318464.3380585

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,499	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	5.4750222e-05
8,490	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	4.499438e-05
11,016	Extending Graph Rules with Oracles	2024	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
88	Common Expression Analysis in Database Applications	1982	SIGMOD	0.00052316625
278	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00029230623
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
1,476	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD	0.00011779092
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
1,756	Graphflow: An Active Graph Database	2017	SIGMOD	0.00010664542
1,775	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010602927
2,450	Functional Dependencies for Graphs	2016	SIGMOD	8.7882979e-05
2,527	Dependencies for Graphs	2017	PODS	8.5954406e-05
2,912	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	7.9130459e-05
3,394	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.1480446e-05
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05
9,564	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.3254416e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,703	Discovering Graph Functional Dependencies	2018	SIGMOD	4.9555163e-05
9,564	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.3254416e-05
5,031	Event Pattern Matching over Graph Streams	2015	VLDB	5.7499783e-05
5,776	Capturing Topology in Graph Pattern Matching	2012	VLDB	5.3309758e-05
11,565	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1945683e-05
1,720	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010779343
2,450	Functional Dependencies for Graphs	2016	SIGMOD	8.7882979e-05
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
8,866	Adding Counting Quantifiers to Graph Patterns	2016	SIGMOD	4.4323126e-05