Substructure Similarity Search in Graph Databases

Summary: Grafil enables substructure similarity search in graphs via indexed, feature-based filtering. Mapping edge relaxation to allowed missing features, it uses a multi-filter of complementary feature sets to prune candidates before comparisons. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h023862c08cd23642
Venue: SIGMOD
Year: 2005
Pagerank: 0.00015732701
Overall Rank: 601 | 95.97%
DOI: 10.1145/1066157.1066244

Incoming Non-self Citations Over Time

Authors

1. Xifeng Yan (University of Illinois Urbana-Champaign)
2. Philip S. Yu (IBM)
3. Jiawei Han (University of Illinois Urbana-Champaign)

BibTeX Citation

@inproceedings{yan_sigmod05,
        title = {{Substructure Similarity Search in Graph Databases}},
        author = {Yan, Xifeng and Yu, Philip S. and Han, Jiawei},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066244},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066244},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
274	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022490994
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
1,374	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00010880336
2,362	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB	8.5746436e-05
2,376	Towards Graph Containment Search and Indexing	2007	VLDB	8.5543073e-05
2,702	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.1177147e-05
2,773	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0351713e-05
3,168	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.5723309e-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,569	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.1987748e-05
3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1706333e-05
4,824	VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework	2013	CIDR	6.3934185e-05
5,444	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1268526e-05
5,880	Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach	2025	SIGMOD	5.9612878e-05
6,027	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	5.9112117e-05
7,969	Periscope/GQ: A Graph Querying Toolkit	2008	VLDB	5.4153733e-05
9,043	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.2315718e-05
9,679	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	5.1430855e-05
9,840	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1230858e-05
9,860	GARUDA: A System for Large-Scale Mining of Statistically Significant Connected Subgraphs	2016	VLDB	5.1178924e-05
10,247	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	5.0525742e-05
12,450	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
192	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025659453
1,216	A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures	2003	VLDB	0.00011490695

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,376	Towards Graph Containment Search and Indexing	2007	VLDB
2	12,450	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB
3	12,272	Efficient Ad-Hoc Graph Inference and Matching in Biological Databases	2017	SIGMOD
4	2,167	An Approximate Search Engine for Structural Databases	2000	SIGMOD
5	3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB
6	6,642	Mining and Indexing Graphs for Supergraph Search	2013	VLDB
7	4,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
8	3,569	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
9	176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
10	3,369	Connected Substructure Similarity Search	2010	SIGMOD