Optimizing query rewrites for keyword-based advertising

ABSTRACT

We consider the problem of query rewrites in the context of pay-per-click search advertising. Given a three-layer graph consisting of queries, query rewrites, and the corresponding ads that can be served for the rewrites, we formulate a family of graph covering problems whose goals are to suggest a subset of ads with the maximum benefit by suggesting rewrites for a given query. We obtain constant-factor approximation algorithms for these covering problems, under two versions of constraints and a realistic notion of ad benefit. We perform experiments on real data and show that our algorithms are capable of outperforming a competitive baseline algorithm in terms of the benefit of the rewrites.

REFERENCES

• 1: I. Antonellis, H. G. Molina, C--C. Chang. Simrank: Query rewriting through link analysis of the click graph. Stanford Computer Science Department Technical Report, 2007.
• 2: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 3: J. Breese, D. Heckerman, C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proc. 14th UAI, pages 43--52, 1998.
• 4: Silviu Cucerzan , Ryen W. White, Query suggestion based on user landing pages, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277953]
• 5: S. C. Deerwester, S. T. Dumais, T. K. Lancaster, G. W. Furnas, R. A. Harshman. Indexing by latent semantic analysis. In JASIS, 41(6):391--407, 1990.
• 6: D. Fain, J. Pedersen. Sponsored search. In Bulletin of the American Society for Information Science and Technology, 2005.
• 7: Uriel Feige , Vahab S. Mirrokni , Jan Vondrak, Maximizing Non-Monotone Submodular Functions, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.461-471, October 21-23, 2007 [doi>10.1109/FOCS.2007.40]
• 8: Lisa Fleischer , Michel X. Goemans , Vahab S. Mirrokni , Maxim Sviridenko, Tight approximation algorithms for maximum general assignment problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.611-620, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109624]
• 9: P. Goundan, A. Schulz. Revisiting the greedy approach to submodular set function maximization. In phManuscript, 2007.
• 10: Jonathan L. Herlocker , Joseph A. Konstan , Al Borchers , John Riedl, An algorithmic framework for performing collaborative filtering, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.230-237, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312682]
• 11: D. S. Hochbaum, A. Pathria. Analysis of the greedy approach in covering problems. Unpublished, 1994.
• 12: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 13: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 14: S. Khot, R. Lipton, E. Markakis, A. Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. In phProc. 1st WINE, pages 92--101, 2005.
• 15: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9]
• 16: Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
• 17: Vahab Mirrokni , Michael Schapira , Jan Vondrak, Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386805]
• 18: G. L. Nemhauser, L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. In phMath. OR, 3(3):177--188, 1978.
• 19: G. L. Nemhauser, L. A. Wolsey, M. L. Fisher. An analysis of approximations for maximizing submodular set functions. phMath. Prog., 14:265--294, 1978.
• 20: Wei Vivian Zhang , Xiaofei He , Benjamin Rey , Rosie Jones, Query rewriting using active learning for sponsored search, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277942]
• 21: W. Zhang, R. Jones. Comparing click logs and editorial labels for training query rewriting. In Workshop on Query Log Analysis, 16th WWW, 2007.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Economics, Experimentation, Theory

Keywords:
greedy algorithm, keyword-based advertising, query rewriting, submodularity