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: 10492
Venue: VLDB
Year: 2011
Pagerank: 6.3279474e-05
Overall Rank: 5,186 | 64.43%
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,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
5,520	Walking in the Cloud: Parallel SimRank at Scale	2016	VLDB	6.1884239e-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
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
364	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00020054172
653	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00015302705
776	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014110016
1,993	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.3421788e-05
2,618	Combating Web Spam with TrustRank	2004	VLDB	8.3380047e-05
4,689	LinkClus: Efficient Clustering via Heterogeneous Semantic Links	2006	VLDB	6.5614634e-05

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	6,446	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD
3	8,212	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
4	169	Efficient Exact Set-Similarity Joins	2006	VLDB
5	2,291	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB
6	1,588	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB
7	1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
8	8,303	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
9	4,061	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
10	9,471	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB