DBScholar

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
h67cc55d33c50d72e
Venue
SIGMOD
Year
2007
Pagerank
0.00020765078
Overall Rank
332 | 97.77%
DOI
10.1145/1247480.1247574

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{cheng_sigmod07,
        title = {{FG-Index: Towards Verification-Free Query Processing on Graph Databases}},
        author = {Cheng, James and Ke, Yiping and Ng, Wilfred and Lu, An},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247574},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247574},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank Citing Paper Year Venue Pagerank
288 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00021969641
355 On Graph Query Optimization in Large Networks 2010 VLDB 0.00020124083
438 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018286607
490 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017438618
657 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.0001505607
783 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014021799
1,100 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00012013426
1,181 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.00011627329
1,244 SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs 2010 VLDB 0.00011353487
1,374 Neighborhood Based Fast Graph Search in Large Networks 2011 SIGMOD 0.00010880336
2,010 Mining Significant Graph Patterns by Leap Search 2008 SIGMOD 9.1914756e-05
2,604 K-Reach: Who is in Your Small World 2012 VLDB 8.2302549e-05
2,702 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.1177147e-05
3,164 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.5771124e-05
3,369 Connected Substructure Similarity Search 2010 SIGMOD 7.3698379e-05
3,499 iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques 2010 VLDB 7.2549774e-05
3,506 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 7.2501249e-05
4,350 Mining Top-K Large Structural Patterns in a Massive Network 2011 VLDB 6.645396e-05
4,817 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 6.3985024e-05
4,824 VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework 2013 CIDR 6.3934185e-05
4,842 REX: Explaining Relationships between Entity Pairs 2012 VLDB 6.3841337e-05
5,477 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 6.1155396e-05
5,478 Towards Proximity Pattern Mining in Large Graphs 2010 SIGMOD 6.1142386e-05
5,645 Repairing Vertex Labels under Neighborhood Constraints 2014 VLDB 6.0533594e-05
6,642 Mining and Indexing Graphs for Supergraph Search 2013 VLDB 5.7238453e-05
6,760 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD 5.6887265e-05
7,206 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 5.5862482e-05
9,043 GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases 2010 SIGMOD 5.2315718e-05
9,840 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.1230858e-05
10,740 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 4.9793485e-05
11,978 MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces 2021 SIGMOD 4.9793485e-05
12,450 Leveraging Graph Dimensions in Online Graph Search 2015 VLDB 4.9793485e-05
12,532 A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery 2013 SIGMOD 4.9793485e-05
12,666 iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques 2011 SIGMOD 4.9793485e-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
50 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00043130126
192 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00025659453
441 A Fast Index for Semistructured Data 2001 VLDB 0.00018215078
740 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00014325275
921 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00013069413
1,023 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00012432693
1,216 A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures 2003 VLDB 0.00011490695
1,350 GraphDB: Modeling and Querying Graphs in Databases 1994 VLDB 0.0001094492
3,383 Mining Compressed Frequent-Pattern Sets 2005 VLDB 7.3552126e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,705 Efficient Temporal Subgraph Management: A New Interval Index 2026 VLDB
2 6,027 Answering Top-k Representative Queries on Graph Databases 2014 SIGMOD
3 2,376 Towards Graph Containment Search and Indexing 2007 VLDB
4 10,642 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD
5 438 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB
6 12,152 An Efficient Index for RDF Query Containment 2019 SIGMOD
7 176 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD
8 6,760 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD
9 3,506 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB
10 736 Graph Indexing: Tree + Delta >= Graph 2007 VLDB