Connected Substructure Similarity Search

Summary: Proposes GrafD-Index for connected substructure search, indexing graphs by feature-distance and deriving a tight distance-triangle inequality. Derives bounds to prune candidates and accelerate verification, with strong experimental gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4365
Venue: SIGMOD
Year: 2010
Pagerank: 7.5353184e-05
Overall Rank: 3,311 | 77.29%
DOI: 10.1145/1807167.1807264

Incoming Non-self Citations Over Time

Authors

1. Haichuan Shang (National ICT Australia; University of New South Wales)
2. Xuemin Lin (National ICT Australia; University of New South Wales)
3. Ying Zhang (University of New South Wales)
4. Jeffrey Xu Yu (Chinese University of Hong Kong)
5. Wei Wang (National ICT Australia; University of New South Wales)

BibTeX Citation

@inproceedings{shang_sigmod10,
        title = {{Connected Substructure Similarity Search}},
        author = {Shang, Haichuan and Lin, Xuemin and Zhang, Ying and Yu, Jeffrey Xu and Wang, Wei},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807264},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807264},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,650	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.2920414e-05
3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.3491042e-05
4,749	VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework	2013	CIDR	6.5250721e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
5,945	GBLENDER: Visual Subgraph Query Formulation Meets Query Processing	2011	SIGMOD	6.0326529e-05
7,152	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	5.6872619e-05
7,848	Data-driven Visual Graph Query Interface Construction and Maintenance: Challenges and Opportunities	2016	VLDB	5.5327238e-05
11,671	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	5.093636e-05
11,840	CATAPULT: Data-driven Selection of Canned Patterns for Efficient Visual Graph Query Formulation	2019	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021152829
431	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018577017
591	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.0001603683
727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014565738
1,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
2,328	Towards Graph Containment Search and Indexing	2007	VLDB	8.745748e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,159	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB
2	7,152	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD
3	9,383	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB
4	3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB
5	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
6	6,520	Mining and Indexing Graphs for Supergraph Search	2013	VLDB
7	2,328	Towards Graph Containment Search and Indexing	2007	VLDB
8	3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
9	4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
10	591	Substructure Similarity Search in Graph Databases	2005	SIGMOD