Database Paper Browser

Back to papers

Graph Pattern Matching: From Intractable to Polynomial Time

Summary: Proposes bounded-hop connectivity and bounded-simulation, relaxing bijective subgraph isomorphism for poly-time graph-pattern matching. Cubic-time matching, incremental updates with DAG guarantees, and scalable experiments show real-network communities. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
10082
Venue
VLDB
Year
2010
Pagerank
0.00012118275
Overall Rank
1,414 | 90.17%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank Citing Paper Year Venue Pagerank
444 Parallelizing Sequential Graph Computations 2017 SIGMOD 0.00022987918
999 Effective Community Search for Large Attributed Graphs 2016 VLDB 0.00014726563
1,285 Neighborhood Based Fast Graph Search in Large Networks 2011 SIGMOD 0.00012833377
1,579 Query Preserving Graph Compression 2012 SIGMOD 0.00011283792
1,720 Incremental Graph Pattern Matching 2011 SIGMOD 0.00010779343
2,162 Scalable Subgraph Enumeration in MapReduce 2015 VLDB 9.3964337e-05
2,551 NeMa: Fast Graph Search with Label Similarity 2013 VLDB 8.5572574e-05
2,770 Keyword Search in Graphs: Finding r-cliques 2011 VLDB 8.1437191e-05
3,232 Managing Large Dynamic Graphs Efficiently 2012 SIGMOD 7.336861e-05
4,807 Diversified Top-k Graph Pattern Matching 2013 VLDB 5.9092289e-05
4,946 Querying Graph Patterns 2011 PODS 5.8149362e-05
5,031 Event Pattern Matching over Graph Streams 2015 VLDB 5.7499783e-05
5,215 Relational Approach for Shortest Path Discovery over Large Graphs 2012 VLDB 5.6228603e-05
5,776 Capturing Topology in Graph Pattern Matching 2012 VLDB 5.3309758e-05
5,852 Repairing Vertex Labels under Neighborhood Constraints 2014 VLDB 5.3007132e-05
5,926 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 5.271318e-05
6,146 Distributed Graph Simulation: Impossibility and Possibility 2014 VLDB 5.1857597e-05
6,152 MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces 2021 SIGMOD 5.183145e-05
6,847 TriAL for RDF: Adapting Graph Query Languages for RDF Data 2013 PODS 4.9089877e-05
6,948 Semantic Acyclicity on Graph Databases 2013 PODS 4.8898337e-05
6,971 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 4.8792893e-05
7,085 Querying Big Data by Accessing Small Data 2015 PODS 4.8388174e-05
7,409 CommunityAF: An Example-based Community Search Method via Autoregressive Flow 2023 VLDB 4.7370979e-05
7,584 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 4.7041255e-05
7,762 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 4.6583829e-05
7,775 Graph Querying Meets HCI: State of the Art and Future Directions 2017 SIGMOD 4.653773e-05
8,210 Mining Top-k Pairs of Correlated Subgraphs in a Large Network 2020 VLDB 4.5581054e-05
8,851 Efficient Approximations of Conjunctive Queries 2012 PODS 4.4363908e-05
10,062 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 4.1945683e-05
10,873 A Single Machine System for Querying Big Graphs with PRAM 2025 VLDB 4.1945683e-05
11,016 Extending Graph Rules with Oracles 2024 VLDB 4.1945683e-05
11,559 Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees 2020 SIGMOD 4.1945683e-05
11,565 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD 4.1945683e-05
11,578 BOOMER: A Tool for Blending Visual P-Homomorphic Queries on Large Networks 2020 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank Cited Paper Year Venue Pagerank
171 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038830709
240 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00031603463
279 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029113513
425 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00023598882
461 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022499343
919 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015343179
2,938 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 7.8524059e-05
3,683 Finding replicated web collections 2000 SIGMOD 6.8477289e-05
5,663 Incremental Maintenance of XML Structural Indexes 2004 SIGMOD 5.3832923e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,561 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00011358946
11,926 Growing a Graph Matching from a Handful of Seeds 2015 VLDB 4.1945683e-05
7,641 Extending Graph Patterns with Conditions 2020 SIGMOD 4.6902655e-05
2,938 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 7.8524059e-05
4,807 Diversified Top-k Graph Pattern Matching 2013 VLDB 5.9092289e-05
5,031 Event Pattern Matching over Graph Streams 2015 VLDB 5.7499783e-05
11,559 Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees 2020 SIGMOD 4.1945683e-05
11,565 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD 4.1945683e-05
5,776 Capturing Topology in Graph Pattern Matching 2012 VLDB 5.3309758e-05
1,720 Incremental Graph Pattern Matching 2011 SIGMOD 0.00010779343