DBScholar

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
3592
Venue
SIGMOD
Year
2004
Pagerank
0.00027100548
Overall Rank
177 | 98.79%
DOI
10.1145/1007568.1007607

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{yan_sigmod04,
        title = {{Graph Indexing: A Frequent Structure-based Approach}},
        author = {Yan, Xifeng and Yu, Philip S. and Han, Jiawei},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007607},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007607},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 62 citing papers.

Rank Citing Paper Year Venue Pagerank
9,496 FIX: Feature-based Indexing Technique for XML Documents 2006 VLDB 5.2611263e-05
9,973 Exploiting Structure in Regular Expression Queries 2023 SIGMOD 5.1845938e-05
10,084 MAVIS: Materialized View for Subgraph Matching 2026 SIGMOD 5.1573064e-05
10,552 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 5.093636e-05
10,558 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 5.093636e-05
11,072 Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds 2025 VLDB 5.093636e-05
11,075 Mix & Match: Subgraph Matching for Absolute Coverage 2025 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
12,741 Computing for Biologists: lessons from some successful case studies 2005 SIGMOD 5.093636e-05
Previous Page 2 / 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
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
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
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,328 Towards Graph Containment Search and Indexing 2007 VLDB
2 12,375 iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques 2011 SIGMOD
3 3,311 Connected Substructure Similarity Search 2010 SIGMOD
4 3,421 Updates for Structure Indexes 2002 VLDB
5 322 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD
6 6,520 Mining and Indexing Graphs for Supergraph Search 2013 VLDB
7 3,477 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB
8 591 Substructure Similarity Search in Graph Databases 2005 SIGMOD
9 727 Graph Indexing: Tree + Delta >= Graph 2007 VLDB
10 2,709 GraphMiner: A Structural Pattern-Mining System for Large Disk-based Graph Databases and Its Applications 2005 SIGMOD