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: 5799
Venue: SIGMOD
Year: 2020
Pagerank: 4.7047078e-05
Overall Rank: 7,566 | 47.42%
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,490	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	5.4788004e-05
8,488	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	4.4951247e-05
11,019	Extending Graph Rules with Oracles	2024	VLDB	4.1905499e-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
89	Common Expression Analysis in Database Applications	1982	SIGMOD	0.00052299473
271	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00029565193
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
1,125	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013829006
1,475	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD	0.00011765071
1,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
1,715	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010776518
1,746	Graphflow: An Active Graph Database	2017	SIGMOD	0.0001069135
2,517	Dependencies for Graphs	2017	PODS	8.6058545e-05
2,882	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	7.9666138e-05
3,439	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.0916563e-05
3,478	Functional Dependencies for Graphs	2016	SIGMOD	7.0554625e-05
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
11,711	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,120	Discovering Graph Functional Dependencies	2018	SIGMOD	4.8200122e-05
11,711	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.1905499e-05
5,017	Event Pattern Matching over Graph Streams	2015	VLDB	5.7505967e-05
5,786	Capturing Topology in Graph Pattern Matching	2012	VLDB	5.3256482e-05
11,569	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1905499e-05
1,806	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010478244
3,478	Functional Dependencies for Graphs	2016	SIGMOD	7.0554625e-05
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
8,786	Adding Counting Quantifiers to Graph Patterns	2016	SIGMOD	4.4467423e-05