A Partition-Based Approach to Structure Similarity Search

Summary: Partition-based, var-size partitions convert edit-distance search to graph containment for candidate generation, addressing vertex degrees. Adds pruning, improved GED, and cost-aware partitioning, yielding gains vs fixed-substructure methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11041
Venue: VLDB
Year: 2014
Pagerank: 7.3491042e-05
Overall Rank: 3,522 | 75.84%
DOI: 10.14778/2732232.2732235

Incoming Non-self Citations Over Time

Authors

1. Xiang Zhao (University of New South Wales)
2. Chuan Xiao (Nagoya University)
3. Xuemin Lin (East China Normal University; University of New South Wales)
4. Qing Liu (Commonwealth Scientific and Industrial Research Organisation)
5. Wenjie Zhang (University of New South Wales)

BibTeX Citation

@article{zhao_vldb14,
        title = {{A Partition-Based Approach to Structure Similarity Search}},
        author = {Zhao, Xiang and Xiao, Chuan and Lin, Xuemin and Liu, Qing and Zhang, Wenjie},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {3},
        pages = {169--180},
        doi = {10.14778/2732232.2732235},
        url = {https://doi.org/10.14778/2732232.2732235},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,168	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.3353772e-05
6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	6.0084322e-05
7,152	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	5.6872619e-05
8,126	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	5.4827332e-05
9,149	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	5.3134506e-05
9,383	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	5.2755515e-05
9,729	Scalable Graph Convolutional Network Training on Distributed-Memory Systems	2023	VLDB	5.2289669e-05
10,939	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
431	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018577017
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
591	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.0001603683
1,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
1,231	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011571594
2,285	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.8052998e-05
2,650	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.2920414e-05
3,311	Connected Substructure Similarity Search	2010	SIGMOD	7.5353184e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB
2	9,383	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB
3	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
4	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
5	4,289	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD
6	1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
7	12,159	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB
8	10,606	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB
9	591	Substructure Similarity Search in Graph Databases	2005	SIGMOD
10	3,311	Connected Substructure Similarity Search	2010	SIGMOD