DBScholar

Back to papers

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
5332
Venue
SIGMOD
Year
2016
Pagerank
6.4910166e-05
Overall Rank
4,825 | 66.90%
DOI
10.1145/2882903.2915243

Incoming Non-self Citations Over Time

Authors

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
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,446 Exact Single-Source SimRank Computation on Large Graphs 2020 SIGMOD 5.8763523e-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,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
Previous Page 1 / 1 Next

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
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
2,291 Efficient Partial-Pairs SimRank Search on Large Networks 2015 VLDB 8.7973939e-05
4,061 Efficient Top-K SimRank-based Similarity Join 2015 VLDB 6.9319591e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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