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
3531
Venue
SIGMOD
Year
2004
Pagerank
0.00034881375
Overall Rank
202 | 98.60%
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
389 Counting Triangles in Data Streams 2006 PODS 0.00024649634
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
576 Substructure Similarity Search in Graph Databases 2005 SIGMOD 0.00019858777
616 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00019068362
749 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017193776
895 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015498104
916 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015326675
949 Comparing Stars: On Approximating Graph Edit Distance 2009 VLDB 0.0001510288
1,095 GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph 2014 VLDB 0.00014103799
1,125 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00013829006
1,280 Neighborhood Based Fast Graph Search in Large Networks 2011 SIGMOD 0.00012838714
1,334 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00012543633
1,444 SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs 2010 VLDB 0.00011941836
1,522 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.0001152219
1,630 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.00011073047
1,715 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00010776518
1,720 Mining Significant Graph Patterns by Leap Search 2008 SIGMOD 0.00010757565
1,962 Exemplar Queries: Give me an Example of What You Need 2014 VLDB 9.9463687e-05
2,199 gStore: Answering SPARQL Queries via Subgraph Matching 2011 VLDB 9.3082437e-05
2,402 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.87387e-05
2,418 VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework 2013 CIDR 8.8499974e-05
2,432 Towards Graph Containment Search and Indexing 2007 VLDB 8.8247178e-05
2,524 Connected Substructure Similarity Search 2010 SIGMOD 8.5993622e-05
3,119 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 7.5393376e-05
3,707 iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques 2010 VLDB 6.8223857e-05
3,873 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 6.673504e-05
3,894 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 6.6531173e-05
4,321 Mining Top-K Large Structural Patterns in a Massive Network 2011 VLDB 6.2821897e-05
4,713 Mining Graph Patterns Efficiently via Randomized Summaries 2009 VLDB 5.9694403e-05
4,955 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 5.8057282e-05
4,959 Efficient Subgraph Search over Large Uncertain Graphs 2011 VLDB 5.7992713e-05
5,002 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 5.7610359e-05
5,158 Towards Proximity Pattern Mining in Large Graphs 2010 SIGMOD 5.6510256e-05
5,502 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 5.4730826e-05
5,778 Graph-Aware, Workload-Adaptive SPARQL Query Caching 2015 SIGMOD 5.3274776e-05
5,871 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 5.2912806e-05
5,903 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 5.2757528e-05
5,968 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 5.2469955e-05
6,386 Mining and Indexing Graphs for Supergraph Search 2013 VLDB 5.0820608e-05
6,436 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.0554554e-05
6,705 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9507418e-05
6,870 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD 4.8974284e-05
6,921 Efficient Indexing and Querying over Syntactically Annotated Trees 2012 VLDB 4.8878659e-05
7,091 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 4.8304411e-05
7,256 CAVE: Concurrency-Aware Graph Processing on SSDs 2024 SIGMOD 4.7819929e-05
7,321 Periscope/GQ: A Graph Querying Toolkit 2008 VLDB 4.7577703e-05
8,488 A Framework for Privacy Preserving Localized Graph Pattern Query Processing 2023 SIGMOD 4.4951247e-05
8,723 GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases 2010 SIGMOD 4.4546285e-05
9,315 FIX: Feature-based Indexing Technique for XML Documents 2006 VLDB 4.352917e-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.00064281097
172 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038837872
414 A Fast Index for Semistructured Data 2001 VLDB 0.00023801668
750 A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures 2003 VLDB 0.0001718364
864 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00015781693
993 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00014759406
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,432 Towards Graph Containment Search and Indexing 2007 VLDB 8.8247178e-05
12,188 iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques 2011 SIGMOD 4.1905499e-05
2,524 Connected Substructure Similarity Search 2010 SIGMOD 8.5993622e-05
3,468 Updates for Structure Indexes 2002 VLDB 7.0634268e-05
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027077424
6,386 Mining and Indexing Graphs for Supergraph Search 2013 VLDB 5.0820608e-05
3,894 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 6.6531173e-05
576 Substructure Similarity Search in Graph Databases 2005 SIGMOD 0.00019858777
895 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015498104
816 GraphMiner: A Structural Pattern-Mining System for Large Disk-based Graph Databases and Its Applications 2005 SIGMOD 0.00016287952