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: h8367b2a0be1c43ad
Venue: SIGMOD
Year: 2010
Pagerank: 7.3548555e-05
Overall Rank: 3,366 | 77.44%
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,705	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.0936619e-05
3,582	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.1715746e-05
4,843	VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework	2013	CIDR	6.3731613e-05
5,467	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1037173e-05
6,084	GBLENDER: Visual Subgraph Query Formulation Meets Query Processing	2011	SIGMOD	5.8750138e-05
7,226	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	5.5651409e-05
8,021	Data-driven Visual Graph Query Interface Construction and Maintenance: Challenges and Opportunities	2016	VLDB	5.3890522e-05
9,615	CATAPULT: Data-driven Selection of Canned Patterns for Efficient Visual Graph Query Formulation	2019	SIGMOD	5.1376962e-05
12,028	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.9605343e-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
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026634326
333	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020712452
439	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018247958
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015699993
734	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014334121
1,136	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011857445
2,387	Towards Graph Containment Search and Indexing	2007	VLDB	8.5236741e-05

Semantically Similar Papers

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