SLING: A Near-Optimal Index Structure for SimRank

Summary: SLING is a near-optimal SimRank index with eps additive error guarantees; single-pair queries run in O(1/eps) and single-source in O(n/eps). Space O(n/eps); precomputation O(m/eps + n log n delta/eps^2); on real graphs, up to 10k× (single-pair) and 110× (single-source) speedups at higher space. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h67769d35d8f6f2d1
Venue: SIGMOD
Year: 2016
Pagerank: 6.3454989e-05
Overall Rank: 4,941 | 66.79%
DOI: 10.1145/2882903.2915243

Incoming Non-self Citations Over Time

Authors

1. Boyu Tian (Shanghai Jiao Tong University)
2. Xiaokui Xiao (Nanyang Technological University)

BibTeX Citation

@inproceedings{tian_sigmod16,
        title = {{SLING: A Near-Optimal Index Structure for SimRank}},
        author = {Tian, Boyu and Xiao, Xiaokui},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915243},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915243},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,031	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	6.84057e-05
5,945	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	5.9384932e-05
6,581	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD	5.7445028e-05
7,986	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	5.4123815e-05
8,379	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	5.3432239e-05
9,492	DISK: A Distributed Framework for Single-Source SimRank with Accuracy Guarantee	2021	VLDB	5.1708619e-05
9,628	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	5.1476979e-05
11,698	ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy Guarantee	2023	SIGMOD	4.9793485e-05
12,098	SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits	2020	VLDB	4.9793485e-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
666	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00014985082
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013980547
1,400	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00010776946
1,626	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB	0.00010043754
1,864	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.4824224e-05
2,345	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB	8.6034897e-05
4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	6.7794413e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,031	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
2	4,303	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
3	1,626	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB
4	7,986	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB
5	4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
6	9,628	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
7	8,379	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
8	6,581	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD
9	1,400	Scalable Similarity Search for SimRank	2014	SIGMOD
10	5,945	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB