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
3907
Venue
SIGMOD
Year
2007
Pagerank
0.00026351742
Overall Rank
351 | 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
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
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
916 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015326675
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,444 SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs 2010 VLDB 0.00011941836
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
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,524 Connected Substructure Similarity Search 2010 SIGMOD 8.5993622e-05
2,762 K-Reach: Who is in Your Small World 2012 VLDB 8.1614818e-05
3,707 iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques 2010 VLDB 6.8223857e-05
3,894 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 6.6531173e-05
4,064 REX: Explaining Relationships between Entity Pairs 2012 VLDB 6.4763384e-05
4,321 Mining Top-K Large Structural Patterns in a Massive Network 2011 VLDB 6.2821897e-05
4,326 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 6.2772512e-05
5,158 Towards Proximity Pattern Mining in Large Graphs 2010 SIGMOD 5.6510256e-05
5,871 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 5.2912806e-05
5,881 Repairing Vertex Labels under Neighborhood Constraints 2014 VLDB 5.2872198e-05
5,903 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 5.2757528e-05
6,386 Mining and Indexing Graphs for Supergraph Search 2013 VLDB 5.0820608e-05
6,835 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 4.9065543e-05
6,870 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD 4.8974284e-05
8,723 GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases 2010 SIGMOD 4.4546285e-05
9,523 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 4.3273374e-05
10,270 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 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,969 Leveraging Graph Dimensions in Online Graph Search 2015 VLDB 4.1905499e-05
12,051 A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery 2013 SIGMOD 4.1905499e-05
12,188 iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques 2011 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
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
812 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00016343476
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
1,327 GraphDB: Modeling and Querying Graphs in Databases 1994 VLDB 0.00012571112
3,061 Mining Compressed Frequent-Pattern Sets 2005 VLDB 7.6389596e-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.1905499e-05
6,085 Answering Top-k Representative Queries on Graph Databases 2014 SIGMOD 5.2165029e-05
2,432 Towards Graph Containment Search and Indexing 2007 VLDB 8.8247178e-05
10,166 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
616 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00019068362
11,662 An Efficient Index for RDF Query Containment 2019 SIGMOD 4.1905499e-05
202 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00034881375
6,870 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD 4.8974284e-05
3,894 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 6.6531173e-05
895 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015498104