Database Paper Browser

Back to papers

Graph Indexing: A Frequent Structure-based Approach

Summary: gIndex uses frequent substructures as the indexing feature, replacing path-based graph indexing. It yields ~10× smaller index and 3–10× faster queries than GraphGrep, with stable updates; extends to sequences/trees, illustrating mining-based indexing. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3530
Venue
SIGMOD
Year
2004
Pagerank
0.00034889335
Overall Rank
203 | 98.59%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 62 citing papers.

Rank Citing Paper Year Venue Pagerank
392 Counting Triangles in Data Streams 2006 PODS 0.00024556183
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
572 Substructure Similarity Search in Graph Databases 2005 SIGMOD 0.00019887011
612 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.0001920234
764 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017018712
900 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015495155
919 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015343179
951 Comparing Stars: On Approximating Graph Edit Distance 2009 VLDB 0.00015106325
1,089 GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph 2014 VLDB 0.00014157922
1,180 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00013456907
1,285 Neighborhood Based Fast Graph Search in Large Networks 2011 SIGMOD 0.00012833377
1,333 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00012523806
1,454 SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs 2010 VLDB 0.00011913289
1,561 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00011358946
1,635 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.0001105793
1,747 Mining Significant Graph Patterns by Leap Search 2008 SIGMOD 0.00010691242
1,775 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00010602927
1,958 Exemplar Queries: Give me an Example of What You Need 2014 VLDB 9.9572632e-05
2,196 gStore: Answering SPARQL Queries via Subgraph Matching 2011 VLDB 9.3089621e-05
2,409 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.8776858e-05
2,428 VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework 2013 CIDR 8.8367608e-05
2,438 Towards Graph Containment Search and Indexing 2007 VLDB 8.8214248e-05
2,525 Connected Substructure Similarity Search 2010 SIGMOD 8.5981082e-05
3,187 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 7.4136521e-05
3,720 iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques 2010 VLDB 6.8192237e-05
3,873 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 6.6779082e-05
4,072 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 6.4727847e-05
4,330 Mining Top-K Large Structural Patterns in a Massive Network 2011 VLDB 6.2839861e-05
4,716 Mining Graph Patterns Efficiently via Randomized Summaries 2009 VLDB 5.9755569e-05
4,949 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 5.8113132e-05
4,958 Efficient Subgraph Search over Large Uncertain Graphs 2011 VLDB 5.8031038e-05
5,009 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 5.761237e-05
5,159 Towards Proximity Pattern Mining in Large Graphs 2010 SIGMOD 5.6587631e-05
5,728 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 5.3507988e-05
5,771 Graph-Aware, Workload-Adaptive SPARQL Query Caching 2015 SIGMOD 5.3325981e-05
5,854 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 5.3006473e-05
5,877 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 5.2916612e-05
6,152 MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces 2021 SIGMOD 5.183145e-05
6,281 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 5.128862e-05
6,406 Mining and Indexing Graphs for Supergraph Search 2013 VLDB 5.0765917e-05
6,441 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.0603113e-05
6,704 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9554912e-05
6,801 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD 4.9226813e-05
6,919 Efficient Indexing and Querying over Syntactically Annotated Trees 2012 VLDB 4.8925595e-05
7,100 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 4.8326259e-05
7,257 CAVE: Concurrency-Aware Graph Processing on SSDs 2024 SIGMOD 4.786584e-05
7,325 Periscope/GQ: A Graph Querying Toolkit 2008 VLDB 4.7616954e-05
8,490 A Framework for Privacy Preserving Localized Graph Pattern Query Processing 2023 SIGMOD 4.499438e-05
8,726 GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases 2010 SIGMOD 4.4593116e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank Cited Paper Year Venue Pagerank
61 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00064329285
171 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038830709
415 A Fast Index for Semistructured Data 2001 VLDB 0.00023814619
753 A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures 2003 VLDB 0.0001719168
869 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00015788339
993 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00014765816
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,438 Towards Graph Containment Search and Indexing 2007 VLDB 8.8214248e-05
12,180 iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques 2011 SIGMOD 4.1945683e-05
2,525 Connected Substructure Similarity Search 2010 SIGMOD 8.5981082e-05
3,466 Updates for Structure Indexes 2002 VLDB 7.0695018e-05
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027081079
6,406 Mining and Indexing Graphs for Supergraph Search 2013 VLDB 5.0765917e-05
4,072 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 6.4727847e-05
572 Substructure Similarity Search in Graph Databases 2005 SIGMOD 0.00019887011
900 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015495155
820 GraphMiner: A Structural Pattern-Mining System for Large Disk-based Graph Databases and Its Applications 2005 SIGMOD 0.00016289354