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: 3531
Venue: SIGMOD
Year: 2004
Pagerank: 0.00034881375
Overall Rank: 202 | 98.60%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 62 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,561	T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph	2023	SIGMOD	4.3212967e-05
9,825	Exploiting Structure in Regular Expression Queries	2023	SIGMOD	4.2710095e-05
9,935	MAVIS: Materialized View for Subgraph Matching	2026	SIGMOD	4.2456012e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.1905499e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1905499e-05
10,852	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	4.1905499e-05
10,855	Mix & Match: Subgraph Matching for Absolute Coverage	2025	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
12,557	Computing for Biologists: lessons from some successful case studies	2005	SIGMOD	4.1905499e-05

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
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
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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,432	Towards Graph Containment Search and Indexing	2007	VLDB	8.8247178e-05
12,188	iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques	2011	SIGMOD	4.1905499e-05
2,524	Connected Substructure Similarity Search	2010	SIGMOD	8.5993622e-05
3,468	Updates for Structure Indexes	2002	VLDB	7.0634268e-05
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027077424
6,386	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.0820608e-05
3,894	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.6531173e-05
576	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019858777
895	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015498104
816	GraphMiner: A Structural Pattern-Mining System for Large Disk-based Graph Databases and Its Applications	2005	SIGMOD	0.00016287952