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: 3530
Venue: SIGMOD
Year: 2004
Pagerank: 0.00034889335
Overall Rank: 203 | 98.59%
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,310	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	4.3570863e-05
9,561	T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph	2023	SIGMOD	4.3254416e-05
9,826	Exploiting Structure in Regular Expression Queries	2023	SIGMOD	4.2751057e-05
9,934	MAVIS: Materialized View for Subgraph Matching	2026	SIGMOD	4.2496728e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.1945683e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1945683e-05
10,848	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	4.1945683e-05
10,851	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.1945683e-05
11,961	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB	4.1945683e-05
12,043	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD	4.1945683e-05
12,180	iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques	2011	SIGMOD	4.1945683e-05
12,548	Computing for Biologists: lessons from some successful case studies	2005	SIGMOD	4.1945683e-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.00064329285
171	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00038830709
415	A Fast Index for Semistructured Data	2001	VLDB	0.00023814619
753	A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures	2003	VLDB	0.0001719168
869	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00015788339
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014765816

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,438	Towards Graph Containment Search and Indexing	2007	VLDB	8.8214248e-05
12,180	iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques	2011	SIGMOD	4.1945683e-05
2,525	Connected Substructure Similarity Search	2010	SIGMOD	8.5981082e-05
3,466	Updates for Structure Indexes	2002	VLDB	7.0695018e-05
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027081079
6,406	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.0765917e-05
4,072	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.4727847e-05
572	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019887011
900	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015495155
820	GraphMiner: A Structural Pattern-Mining System for Large Disk-based Graph Databases and Its Applications	2005	SIGMOD	0.00016289354