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
10083
Venue
VLDB
Year
2010
Pagerank
0.00012072488
Overall Rank
1,419 | 90.14%
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
441 Parallelizing Sequential Graph Computations 2017 SIGMOD 0.00023172424
1,000 Effective Community Search for Large Attributed Graphs 2016 VLDB 0.00014714977
1,280 Neighborhood Based Fast Graph Search in Large Networks 2011 SIGMOD 0.00012838714
1,572 Query Preserving Graph Compression 2012 SIGMOD 0.00011296109
1,806 Incremental Graph Pattern Matching 2011 SIGMOD 0.00010478244
2,172 Scalable Subgraph Enumeration in MapReduce 2015 VLDB 9.37776e-05
2,557 NeMa: Fast Graph Search with Label Similarity 2013 VLDB 8.5484449e-05
2,774 Keyword Search in Graphs: Finding r-cliques 2011 VLDB 8.140768e-05
3,234 Managing Large Dynamic Graphs Efficiently 2012 SIGMOD 7.3302974e-05
4,748 Diversified Top-k Graph Pattern Matching 2013 VLDB 5.9432853e-05
4,949 Querying Graph Patterns 2011 PODS 5.8090034e-05
5,017 Event Pattern Matching over Graph Streams 2015 VLDB 5.7505967e-05
5,221 Relational Approach for Shortest Path Discovery over Large Graphs 2012 VLDB 5.6180753e-05
5,786 Capturing Topology in Graph Pattern Matching 2012 VLDB 5.3256482e-05
5,881 Repairing Vertex Labels under Neighborhood Constraints 2014 VLDB 5.2872198e-05
5,921 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 5.2681722e-05
6,119 Distributed Graph Simulation: Impossibility and Possibility 2014 VLDB 5.1991813e-05
6,846 TriAL for RDF: Adapting Graph Query Languages for RDF Data 2013 PODS 4.9042778e-05
6,945 Semantic Acyclicity on Graph Databases 2013 PODS 4.8874695e-05
6,965 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 4.8759021e-05
7,061 Querying Big Data by Accessing Small Data 2015 PODS 4.8400281e-05
7,408 CommunityAF: An Example-based Community Search Method via Autoregressive Flow 2023 VLDB 4.7325545e-05
7,588 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 4.6996269e-05
7,761 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 4.6543114e-05
7,777 Graph Querying Meets HCI: State of the Art and Future Directions 2017 SIGMOD 4.6493104e-05
8,209 Mining Top-k Pairs of Correlated Subgraphs in a Large Network 2020 VLDB 4.5537353e-05
8,850 Efficient Approximations of Conjunctive Queries 2012 PODS 4.4324268e-05
10,062 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 4.1905499e-05
10,877 A Single Machine System for Querying Big Graphs with PRAM 2025 VLDB 4.1905499e-05
11,019 Extending Graph Rules with Oracles 2024 VLDB 4.1905499e-05
11,477 MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces 2021 SIGMOD 4.1905499e-05
11,563 Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees 2020 SIGMOD 4.1905499e-05
11,569 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD 4.1905499e-05
11,582 BOOMER: A Tool for Blending Visual P-Homomorphic Queries on Large Networks 2020 SIGMOD 4.1905499e-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
172 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038837872
239 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00031581944
280 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029092277
425 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00023592024
460 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022679846
916 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015326675
2,943 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 7.8463193e-05
3,685 Finding replicated web collections 2000 SIGMOD 6.8392492e-05
5,679 Incremental Maintenance of XML Structural Indexes 2004 SIGMOD 5.3760807e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,522 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.0001152219
11,934 Growing a Graph Matching from a Handful of Seeds 2015 VLDB 4.1905499e-05
7,566 Extending Graph Patterns with Conditions 2020 SIGMOD 4.7047078e-05
2,943 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 7.8463193e-05
4,748 Diversified Top-k Graph Pattern Matching 2013 VLDB 5.9432853e-05
5,017 Event Pattern Matching over Graph Streams 2015 VLDB 5.7505967e-05
11,563 Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees 2020 SIGMOD 4.1905499e-05
11,569 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD 4.1905499e-05
5,786 Capturing Topology in Graph Pattern Matching 2012 VLDB 5.3256482e-05
1,806 Incremental Graph Pattern Matching 2011 SIGMOD 0.00010478244