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: h8ffcfbf36efb149d
Venue: VLDB
Year: 2014
Pagerank: 7.1987748e-05
Overall Rank: 3,569 | 76.01%
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,290	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.1937978e-05
6,137	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.8736299e-05
7,206	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	5.5862482e-05
8,231	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	5.3722895e-05
9,235	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	5.2056825e-05
9,323	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	5.1942311e-05
9,568	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	5.1571823e-05
9,900	Scalable Graph Convolutional Network Training on Distributed-Memory Systems	2023	VLDB	5.1116429e-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
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015732701
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011898162
1,244	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011353487
2,235	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7779518e-05
2,702	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.1177147e-05
3,369	Connected Substructure Similarity Search	2010	SIGMOD	7.3698379e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB
2	9,568	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB
3	3,108	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
4	176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
5	4,139	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD
6	1,864	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
7	12,450	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB
8	11,053	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB
9	601	Substructure Similarity Search in Graph Databases	2005	SIGMOD
10	3,369	Connected Substructure Similarity Search	2010	SIGMOD