Efficient Partial-Pairs SimRank Search on Large Networks

Summary: Introduces a self-contained “seed germination” framework for partial-pairs SimRank, avoiding precomputed h-go scores and pruning unnecessary edge accesses. Supports all-pairs and single-source cases, achieving up to 38× speedups on graphs with tens of millions of links. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11356
Venue: VLDB
Year: 2015
Pagerank: 8.7973939e-05
Overall Rank: 2,291 | 84.29%
DOI: 10.14778/2735479.2735489

Incoming Non-self Citations Over Time

Authors

1. Weiren Yu (Imperial College London)
2. Julie A. McCann (Imperial College London)

BibTeX Citation

@article{yu_vldb15,
        title = {{Efficient Partial-Pairs SimRank Search on Large Networks}},
        author = {Yu, Weiren and McCann, Julie A.},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {5},
        pages = {569},
        doi = {10.14778/2735479.2735489},
        url = {https://doi.org/10.14778/2735479.2735489},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,951	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	6.9974506e-05
4,825	SLING: A Near-Optimal Index Structure for SimRank	2016	SIGMOD	6.4910166e-05
5,520	Walking in the Cloud: Parallel SimRank at Scale	2016	VLDB	6.1884239e-05
5,826	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	6.074674e-05
6,446	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD	5.8763523e-05
6,634	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB	5.8182573e-05
8,212	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	5.4658632e-05
8,213	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	5.4658632e-05
9,314	DISK: A Distributed Framework for Single-Source SimRank with Accuracy Guarantee	2021	VLDB	5.289545e-05
9,471	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	5.2634238e-05
10,281	PJsim: Towards Precise and Scalable Graph Similarity	2026	SIGMOD	5.093636e-05
11,383	ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy Guarantee	2023	SIGMOD	5.093636e-05
11,796	SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits	2020	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
653	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00015302705
758	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00014277369
1,365	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00011017467
1,588	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB	0.0001026895
1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.6948178e-05
5,186	On Link-based Similarity Join	2011	VLDB	6.3279474e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,212	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
2	4,216	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
3	6,634	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
4	6,446	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD
5	1,365	Scalable Similarity Search for SimRank	2014	SIGMOD
6	8,303	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
7	1,588	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB
8	4,061	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
9	9,471	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
10	1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB