Database Paper Browser

Back to papers

FG-Index: Towards Verification-Free Query Processing on Graph Databases

Summary: FG-index builds a nested inverted-index from Frequent subGraphs to enable verification-free graph query processing, returning exact answers for frequent queries and near-exact candidates otherwise. It introduces delta-Tolerance Closed Frequent Graphs (delta-TCFGs) to bound in-memory index size, delivering orders-of-magnitude speedups over state-of-the-art indexes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3906
Venue
SIGMOD
Year
2007
Pagerank
0.00026365067
Overall Rank
350 | 97.57%
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
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
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
919 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015343179
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,454 SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs 2010 VLDB 0.00011913289
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
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,525 Connected Substructure Similarity Search 2010 SIGMOD 8.5981082e-05
2,756 K-Reach: Who is in Your Small World 2012 VLDB 8.1682536e-05
3,720 iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques 2010 VLDB 6.8192237e-05
4,063 REX: Explaining Relationships between Entity Pairs 2012 VLDB 6.4825871e-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,470 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 6.1557462e-05
5,159 Towards Proximity Pattern Mining in Large Graphs 2010 SIGMOD 5.6587631e-05
5,852 Repairing Vertex Labels under Neighborhood Constraints 2014 VLDB 5.3007132e-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,406 Mining and Indexing Graphs for Supergraph Search 2013 VLDB 5.0765917e-05
6,801 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD 4.9226813e-05
6,839 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 4.9109527e-05
8,726 GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases 2010 SIGMOD 4.4593116e-05
9,580 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 4.3234342e-05
10,270 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 4.1945683e-05
11,961 Leveraging Graph Dimensions in Online Graph Search 2015 VLDB 4.1945683e-05
12,043 A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery 2013 SIGMOD 4.1945683e-05
12,180 iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques 2011 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
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
817 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00016352717
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
1,327 GraphDB: Modeling and Querying Graphs in Databases 1994 VLDB 0.00012569127
3,055 Mining Compressed Frequent-Pattern Sets 2005 VLDB 7.6448739e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
10,232 Efficient Temporal Subgraph Management: A New Interval Index 2026 VLDB 4.1945683e-05
6,080 Answering Top-k Representative Queries on Graph Databases 2014 SIGMOD 5.2214553e-05
2,438 Towards Graph Containment Search and Indexing 2007 VLDB 8.8214248e-05
10,166 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
612 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.0001920234
11,657 An Efficient Index for RDF Query Containment 2019 SIGMOD 4.1945683e-05
203 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00034889335
6,801 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD 4.9226813e-05
4,072 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 6.4727847e-05
900 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015495155