An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs

Summary: TSF enables fast SimRank top-k search on large dynamic graphs via two-stage random-walk sampling and compact one-way-graph indexes. Incremental index updates, connectivity-based pruning, probabilistic score guarantees, and disk storage scale to billion-edge graphs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11382
Venue: VLDB
Year: 2015
Pagerank: 6.8273894e-05
Overall Rank: 4,216 | 71.08%
DOI: 10.14778/2757807.2757809

Incoming Non-self Citations Over Time

Authors

1. Yingxia Shao (Peking University)
2. Bin Cui (Peking University)
3. Lei Chen (Hong Kong University of Science and Technology)
4. Mingming Liu (Peking University)
5. Xing Xie (Microsoft)

BibTeX Citation

@article{shao_vldb15,
        title = {{An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs}},
        author = {Shao, Yingxia and Cui, Bin and Chen, Lei and Liu, Mingming and Xie, Xing},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {8},
        pages = {838--849},
        doi = {10.14778/2757807.2757809},
        url = {https://doi.org/10.14778/2757807.2757809},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 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
5,826	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	6.074674e-05
6,423	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD	5.8813146e-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
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 5 of 5 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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,815	Reverse Top-k Search using Random Walk with Restart	2014	VLDB
2	9,471	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
3	6,446	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD
4	8,213	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB
5	1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
6	4,061	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
7	6,634	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
8	8,303	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
9	3,951	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
10	1,365	Scalable Similarity Search for SimRank	2014	SIGMOD