On Link-based Similarity Join

Summary: Proposes LS-join, extending similarity join to link-based measures via an e-function generalizing PPR and SimRank. Offers an efficient LS-join for large graphs and reduces random-walk cost in PPR/SR; validated on three real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h78d5274b6f1aebea
Venue: VLDB
Year: 2011
Pagerank: 6.1865348e-05
Overall Rank: 5,309 | 64.31%
DOI: 10.14778/3402707.3402712

Incoming Non-self Citations Over Time

Authors

1. Liwen Sun (University of Hong Kong)
2. Reynold Cheng (University of Hong Kong)
3. Xiang Li (University of Hong Kong)
4. David W. Cheung (University of Hong Kong)
5. Jiawei Han (University of Illinois Urbana-Champaign)

BibTeX Citation

@article{sun_vldb11,
        title = {{On Link-based Similarity Join}},
        author = {Sun, Liwen and Cheng, Reynold and Li, Xiang and Cheung, David W. and Han, Jiawei},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {11},
        pages = {714--725},
        doi = {10.14778/3402707.3402712},
        url = {https://doi.org/10.14778/3402707.3402712},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
5,647	Walking in the Cloud: Parallel SimRank at Scale	2016	VLDB	6.0524588e-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
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
375	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00019628745
666	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00014985082
783	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014021799
1,996	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.216723e-05
2,668	Combating Web Spam with TrustRank	2004	VLDB	8.1549459e-05
4,785	LinkClus: Efficient Clustering via Heterogeneous Semantic Links	2006	VLDB	6.4150472e-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	6,581	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD
3	8,379	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
4	168	Efficient Exact Set-Similarity Joins	2006	VLDB
5	2,345	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB
6	1,626	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB
7	1,864	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
8	8,471	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
9	4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
10	9,628	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB