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
3968
Venue
SIGMOD
Year
2007
Pagerank
0.00021152829
Overall Rank
326 | 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
294 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022253507
352 On Graph Query Optimization in Large Networks 2010 VLDB 0.00020375193
431 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018577017
485 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017717377
659 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00015214062
776 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014110016
1,102 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00012166591
1,181 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.0001179597
1,231 SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs 2010 VLDB 0.00011571594
1,394 Neighborhood Based Fast Graph Search in Large Networks 2011 SIGMOD 0.0001093153
1,972 Mining Significant Graph Patterns by Leap Search 2008 SIGMOD 9.3708222e-05
2,575 K-Reach: Who is in Your Small World 2012 VLDB 8.3982298e-05
2,650 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.2920414e-05
3,194 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.6491858e-05
3,311 Connected Substructure Similarity Search 2010 SIGMOD 7.5353184e-05
3,431 iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques 2010 VLDB 7.4189541e-05
3,477 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 7.3791229e-05
4,282 Mining Top-K Large Structural Patterns in a Massive Network 2011 VLDB 6.7842201e-05
4,736 REX: Explaining Relationships between Entity Pairs 2012 VLDB 6.5300642e-05
4,748 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 6.5251089e-05
4,749 VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework 2013 CIDR 6.5250721e-05
5,370 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 6.2436385e-05
5,401 Towards Proximity Pattern Mining in Large Graphs 2010 SIGMOD 6.2318138e-05
5,519 Repairing Vertex Labels under Neighborhood Constraints 2014 VLDB 6.1885644e-05
6,520 Mining and Indexing Graphs for Supergraph Search 2013 VLDB 5.8535203e-05
6,631 Updating Graph Indices with a One-Pass Algorithm 2015 SIGMOD 5.8190404e-05
7,152 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 5.6872619e-05
8,884 GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases 2010 SIGMOD 5.3514928e-05
9,665 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.2406724e-05
10,558 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 5.093636e-05
11,671 MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces 2021 SIGMOD 5.093636e-05
12,159 Leveraging Graph Dimensions in Online Graph Search 2015 VLDB 5.093636e-05
12,241 A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery 2013 SIGMOD 5.093636e-05
12,375 iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques 2011 SIGMOD 5.093636e-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
48 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00044033592
187 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00026138589
430 A Fast Index for Semistructured Data 2001 VLDB 0.00018600166
718 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00014642961
897 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00013339862
1,008 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00012688008
1,196 A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures 2003 VLDB 0.00011714981
1,359 GraphDB: Modeling and Querying Graphs in Databases 1994 VLDB 0.00011040427
3,324 Mining Compressed Frequent-Pattern Sets 2005 VLDB 7.5198821e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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