More Web Proxy on the site http://driver.im/

research-article

Simrank++: query rewriting through link analysis of the click graph

Authors:

Ioannis Antonellis,

Hector Garcia Molina,

Chi Chao ChangAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 1, Issue 1

Pages 408 - 421

https://doi.org/10.14778/1453856.1453903

Published: 01 August 2008 Publication History

Abstract

We focus on the problem of query rewriting for sponsored search. We base rewrites on a historical click graph that records the ads that have been clicked on in response to past user queries. Given a query q, we first consider Simrank [7] as a way to identify queries similar to q, i.e., queries whose ads a user may be interested in. We argue that Simrank fails to properly identify query similarities in our application, and we present two enhanced versions of Simrank: one that exploits weights on click graph edges and another that exploits "evidence." We experimentally evaluate our new schemes against Simrank, using actual click graphs and queries from Yahoo!, and using a variety of metrics. Our results show that the enhanced methods can yield more and better query rewrites.

References

[1]

Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In FOCS '06.

Digital Library

[2]

I. Antonellis, H. Garcia-Molina, and C. Chang. Simrank++: Query rewriting through link analysis of the click graph. In Technical Report, url: http://dbpubs.stanford.edu/pub/2007--32, 2007.

[3]

Doug Beeferman and Adam Berger. Agglomerative clustering of a search engine query log. In KDD '00.

Digital Library

[4]

Nick Craswell and Martin Szummer. Random walks on the click graph. In Proc. SIGIR '07.

Digital Library

[5]

Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI 2004.

Digital Library

[6]

S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. 1990.

[7]

Glen Jeh and Jennifer Widom. Simrank: a measure of structural-context similarity. In KDD '02.

Digital Library

[8]

Rosie Jones and Daniel C. Fain. Query word deletion prediction. In SIGIR '03.

Digital Library

[9]

Rosie Jones, Benjamin Rey, Omid Madani, and Wiley Greiner. Generating query substitutions. In WWW '07.

Digital Library

[10]

Christos H. Papadimitriou, Hisao Tamaki, Prabhakar Raghavan, and Santosh Vempala. Latent semantic indexing: a probabilistic analysis. In PODS '98.

Digital Library

[11]

M. Regelson and D. Fain. Predicting click-through rate using keyword clusters. In Proc. 2nd Workshop on Sponsored Search Auctions.

[12]

Matthew Richardson, Ewa Dominowska, and Robert Ragno. Predicting clicks: Estimating the click-through rate for new ads. In WWW '07.

Digital Library

[13]

Ian Ruthven. Re-examining the potential effectiveness of interactive query expansion. In SIGIR '03, pages 213--220.

Digital Library

[14]

A. Sinclair. Algorithms for random generation and counting: A markov chain approach. In Birkhauser, Boston-Basel-Berlin, 1993.

Digital Library

[15]

Egidio Terra and Charles L. A. Clarke. Scoring missing terms in information retrieval tasks. In CIKM '04.

Digital Library

[16]

Ji-Rong Wen, Jian-Yun Nie, and Hong-Jiang Zhang. Query clustering using user logs. ACM Trans. Inf. Syst., 2002.

Digital Library

[17]

Wei Vivian Zhang, Xiaofei He, Benjamin Rey, and Rosie Jones. Query rewriting using active learning for sponsored search. In SIGIR '07.

Digital Library

[18]

Wei Vivian Zhang and Rosie Jones. Comparing click logs and editorial labels for training query rewriting. In Query Log Analysis Workshop, WWW '07.

Cited By

Wu XXu YZhang WZhang Y(2023)Billion-Scale Bipartite Graph Embedding: A Global-Local Induced ApproachProceedings of the VLDB Endowment10.14778/3626292.362630017:2(175-183)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.14778/3626292.3626300
Mani SHsieh KSegarra SEberl TChandra RAzulai EAnnamalai NBansal DKandula S(2023)Securing Public Clouds using Dynamic Communication GraphsProceedings of the 22nd ACM Workshop on Hot Topics in Networks10.1145/3626111.3628198(272-279)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1145/3626111.3628198
Wang RLi ZZhang DYin QZhao TYin BAbdelzaher T(2022)RETE: Retrieval-Enhanced Temporal Event Forecasting on Unified Query Product Evolutionary GraphProceedings of the ACM Web Conference 202210.1145/3485447.3511974(462-472)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3485447.3511974
Show More Cited By

Index Terms

Simrank++: query rewriting through link analysis of the click graph
1. Information systems
  1. Information retrieval

Recommendations

Simrank++: query rewriting through link analysis of the clickgraph (poster)
WWW '08: Proceedings of the 17th international conference on World Wide Web

We focus on the problem of query rewriting for sponsored search. We base rewrites on a historical click graph that records the ads that have been clicked on in response to past user queries. Given a query q, we first consider Simrank [2] as a way to ...
The comparative effectiveness of sponsored and nonsponsored links for Web e-commerce queries

The predominant business model for Web search engines is sponsored search, which generates billions in yearly revenue. But are sponsored links providing online consumers with relevant choices for products and services? We address this and related issues ...
SimRank*: effective and scalable pairwise similarity search based on graph topology

Given a graph, how can we quantify similarity between two nodes in an effective and scalable wayý SimRank is an attractive measure of pairwise similarity based on graph topologies. Its underpinning philosophy that "two nodes are similar if they are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 1, Issue 1

August 2008

1216 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2008

Published in PVLDB Volume 1, Issue 1

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
789
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu XXu YZhang WZhang Y(2023)Billion-Scale Bipartite Graph Embedding: A Global-Local Induced ApproachProceedings of the VLDB Endowment10.14778/3626292.362630017:2(175-183)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.14778/3626292.3626300
Mani SHsieh KSegarra SEberl TChandra RAzulai EAnnamalai NBansal DKandula S(2023)Securing Public Clouds using Dynamic Communication GraphsProceedings of the 22nd ACM Workshop on Hot Topics in Networks10.1145/3626111.3628198(272-279)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1145/3626111.3628198
Wang RLi ZZhang DYin QZhao TYin BAbdelzaher T(2022)RETE: Retrieval-Enhanced Temporal Event Forecasting on Unified Query Product Evolutionary GraphProceedings of the ACM Web Conference 202210.1145/3485447.3511974(462-472)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3485447.3511974
Luo QYu DMaradapu Vera Venkata Sai ACai ZCheng X(2022)A survey of structural representation learning for social networksNeurocomputing10.1016/j.neucom.2022.04.128496:C(56-71)Online publication date: 28-Jul-2022
https://dl.acm.org/doi/10.1016/j.neucom.2022.04.128
Zhang MYan XWang WDemartini GZuccon GCulpepper JHuang ZTong H(2021)Comprehensively Computing Link-based Similarities by Building A Random Surfer GraphProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482329(2578-2587)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482329
Wen SChen YYang ZZhang YZhang DWang LZheng BDemartini GZuccon GCulpepper JHuang ZTong H(2021)SMADProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482183(3543-3547)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482183
Chodpathumwan YTermehchy ARamsey SShrestha AGlen ALiu ZLi GLi ZIdreos SSrivastava D(2021)Structural Generalizability: The Case of Similarity SearchProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457316(326-338)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457316
Wang HWei ZLiu YYuan YDu XWen J(2021)ExactSim: benchmarking single-source SimRank algorithms with high-precision ground truthsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-021-00672-730:6(989-1015)Online publication date: 5-Jun-2021
https://dl.acm.org/doi/10.1007/s00778-021-00672-7
Chen XLai LQin LLin X(2021)Efficient structural node similarity computation on billion-scale graphsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-021-00654-930:3(471-493)Online publication date: 23-Feb-2021
https://dl.acm.org/doi/10.1007/s00778-021-00654-9
Shi JJin TYang RXiao XYang Y(2020)Realtime index-free single source SimRank processing on web-scale graphsProceedings of the VLDB Endowment10.14778/3384345.338434713:7(966-980)Online publication date: 26-Mar-2020
https://dl.acm.org/doi/10.14778/3384345.3384347
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents