Simrank++: Query Rewriting through Link Analysis of the Click Graph

Summary: Introduces Simrank++ for query rewriting in sponsored search by extending SimRank with edge weights and evidence signals on a historical click graph. Shows these enhancements yield better query rewrites than vanilla Simrank on Yahoo! click data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h29e4235c5e5d9293
Venue: VLDB
Year: 2008
Pagerank: 0.00013980547
Overall Rank: 788 | 94.71%
DOI: 10.14778/1453856.1453902

Incoming Non-self Citations Over Time

Authors

1. Ioannis Antonellis (Stanford University)
2. Hector Garcia-Molina (Stanford University)
3. Chi-Chao Chang (Yahoo)

BibTeX Citation

@article{antonellis_vldb08,
        title = {{Simrank++: Query Rewriting through Link Analysis of the Click Graph}},
        author = {Antonellis, Ioannis and Garcia-Molina, Hector and Chang, Chi-Chao},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {408--419},
        doi = {10.14778/1453856.1453902},
        url = {https://doi.org/10.14778/1453856.1453902},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,400	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00010776946
1,419	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010728945
1,626	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB	0.00010043754
1,798	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.616919e-05
2,102	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0463758e-05
2,345	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB	8.6034897e-05
3,266	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.4775e-05
4,031	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	6.84057e-05
4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	6.7794413e-05
4,303	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	6.6772109e-05
4,941	SLING: A Near-Optimal Index Structure for SimRank	2016	SIGMOD	6.3454989e-05
5,562	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD	6.0841762e-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
6,752	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB	5.6905975e-05
7,986	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	5.4123815e-05
8,077	Billion-Scale Bipartite Graph Embedding: A Global-Local Induced Approach	2024	VLDB	5.3942942e-05
8,379	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	5.3432239e-05
10,263	BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank	2024	VLDB	5.050482e-05
10,493	PJsim: Towards Precise and Scalable Graph Similarity	2026	SIGMOD	4.9793485e-05
11,698	ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy Guarantee	2023	SIGMOD	4.9793485e-05
11,985	Structural Generalizability: The Case of Similarity Search	2021	SIGMOD	4.9793485e-05
12,316	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,141	Latent Semantic Indexing: A Probabilistic Analysis	1998	PODS	0.00011852572

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,578	Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data	2013	VLDB
2	12,098	SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits	2020	VLDB
3	5,945	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB
4	8,379	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
5	6,581	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD
6	7,986	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB
7	6,752	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
8	666	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB
9	1,626	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB
10	9,628	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB