skip to main content
10.1145/1526709.1526778acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Online expansion of rare queries for sponsored search

Published: 20 April 2009 Publication History

Abstract

Sponsored search systems are tasked with matching queries
to relevant advertisements. The current state-of-the-art matching algorithms expand the user's query using a variety of external resources, such as Web search results. While these expansion-based algorithms are highly effective, they are largely inefficient and cannot be applied in real-time. In practice, such algorithms are applied offline to popular queries, with the results of the expensive operations cached for fast access at query time. In this paper, we describe an efficient and effective approach for matching ads against rare queries that were not processed offline. The approach builds an expanded query representation by leveraging offline processing done for related popular queries. Our experimental results show that our approach significantly improves the effectiveness of advertising on rare queries with only a negligible increase in computational cost.

References

[1]
P. Anick. Using terminological feedback for web search refinement: a log-based study. In Proc. 26th Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 88--95, 2003.
[2]
R. A. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison--Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1999.
[3]
B. Billerbeck, F. Scholer, H. Williams, and J. Zobel. Query expansion using associated queries. In Proc. 12th Intl. Conf. on Information and Knowledge Management, pages 2--9, 2003.
[4]
A. Broder, M. Ciaramita, M. Fontoura, E. Gabrilovich, V. Josifovski, D. Metzler, V. Murdock, and V. Plachouras. To swing or not to swing: Learning when (not) to advertise. In Proc 17th. Intl. Conf. on Information and Knowledge Management, pages 1003--1012, 2008.
[5]
A. Broder, P. Ciccolo, M. Fontoura, E. Gabrilovich, V. Josifovski, and L. Riedel. Search advertising using web relevance feedback. In Proc 17th. Intl. Conf. on Information and Knowledge Management, pages 1013--1022, 2008.
[6]
A. Broder, M. Fontoura, V. Josifovski, and L. Riedel. A semantic approach to contextual advertising. In Proc 30th . Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 559--566, 2007.
[7]
S. Cucerzan and E. Brill. Spelling correction as an iterative process that exploits the collective knowledge of web users. In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 293--300, 2004.
[8]
H. Cui, J.-R. Wen, J.-Y. Nie, and W.-Y. Ma. Probabilistic query expansion using query logs. In Proc 11th Intl. Conf. on World Wide Web, pages 325--332, 2002.
[9]
S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
[10]
F. Diaz and D. Metzler. Improving the estimation of relevance models using large external corpora. In Proc. 29th Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 154--161, 2006.
[11]
B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, 2007.
[12]
B. Efron and R. J. Tibshirani. An introduction to the Bootstrap., volume 57 of Monographs on Statistics and Applied Probability. Chapman and Hall, 1993.
[13]
K. Jarvelin and J. Kekalainen. Cumulated gain-based evaluation of ir techniques. ACM Trans. Inf. Syst., 20(4):422--446, 2002.
[14]
R. Jones and D. C. Fain. Query word deletion prediction. In Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 435--436, 2003.
[15]
R. Jones, B. Rey, O. Madani, and W. Greiner. Generating query substitutions. In Proc. 15th Intl. Conf. on World Wide Web, pages 387--396, 2006.
[16]
R. Krovetz. Viewing morphology as an inference process. In Proc 16th Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 191--202, 1993.
[17]
V. Lavrenko and W. B. Croft. Relevance-based language models. In Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 120--127, 2001.
[18]
M. Mitra, A. Singhal, and C. Buckley. Improving automatic query expansion. In Proceedings of the ACM Conference on Research and Development in Information Retrieval (SIGIR), pages 206--214, 1998.
[19]
F. Peng, N. Ahmed, X. Li, and Y. Lu. Context sensitive stemming for web search. In Proc. 30th Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 639--646, 2007.
[20]
M. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
[21]
F. Radlinski, A. Broder, P. Ciccolo, E. Gabrilovich, V. Josifovski, and L. Riedel. Optimizing relevance and revenue in ad search: a query substitution approach. In Proc. 31st Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 403--410, 2008.
[22]
B. Ribeiro-Neto, M. Cristo, P. B. Golgher, and E. S. de Moura. Impedance coupling in content-targeted advertising. In SIGIR'05, 2005.
[23]
S. Robertson and S. Walker. Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In Proc. 17th Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 232--241, 1994.
[24]
S. Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, and M. Gatford. Okapi at TREC-3. In Proc. 3rd Text REtrieval Conference, pages 109--126, 1994.
[25]
S. Robertson, H. Zaragoza, and M. Taylor. Simple bm25 extension to multiple weighted fields. In Proc. 13th Intl. Conf. on Information and Knowledge Management, pages 42--49, 2004.
[26]
J. J. Rocchio. Relevance Feedback in Information Retrieval, pages 313---323. Prentice-Hall, 1971.
[27]
M. Sahami and T. D. Heilman. A web-based kernel function for measuring the similarity of short text snippets. In WWW, 2006.
[28]
A. Spink, D. Wolfram, B. Jansen, and T. Saracevic. Searching the web: The public and their queries. Journal of the American Society for Information Science and Technology, 53(3):226--234, 2001.
[29]
E. M. Voorhees. Query expansion using lexical-semantic relations. In Ann. Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, pages 61--69, 1994.
[30]
C. Wang, P. Zhang, R. Choi, and M. D. Eredita. Understanding consumers attitude toward advertising. In Proceedings of Americas Conference on Information Systems, pages 1143--1148, 2002.
[31]
J. Xu and W. B. Croft. Improving the effectiveness of information retrieval with local context analysis. ACM Transactions on Information Science (TOIS), 18(1):79--112, 2000.
[32]
C. Zhai and J. D. Lafferty. Model-based feedback in the language modeling approach to information retrieval. In Intl. Conf. on Information and Knowledge Management, pages 403--410, 2001.

Cited By

View all
  • (2024)Query Expansion Using Proposed Location-Based Algorithm for Hindi–English CLIR: Analyzing Three Test CollectionsInternational Journal of Pattern Recognition and Artificial Intelligence10.1142/S021800142459001838:05Online publication date: 11-May-2024
  • (2023)The Impact of Large Language Models on Search Advertising: Evidence from Google’s BERTSSRN Electronic Journal10.2139/ssrn.4614402Online publication date: 2023
  • (2023)Eligibility Mechanisms: Auctions Meet Information RetrievalProceedings of the ACM Web Conference 202310.1145/3543507.3583478(3541-3549)Online publication date: 30-Apr-2023
  • Show More Cited By

Index Terms

  1. Online expansion of rare queries for sponsored search

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WWW '09: Proceedings of the 18th international conference on World wide web
    April 2009
    1280 pages
    ISBN:9781605584874
    DOI:10.1145/1526709

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 20 April 2009

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. query expansion
    2. sponsored search
    3. tail queries

    Qualifiers

    • Research-article

    Conference

    WWW '09
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)8
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 22 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Query Expansion Using Proposed Location-Based Algorithm for Hindi–English CLIR: Analyzing Three Test CollectionsInternational Journal of Pattern Recognition and Artificial Intelligence10.1142/S021800142459001838:05Online publication date: 11-May-2024
    • (2023)The Impact of Large Language Models on Search Advertising: Evidence from Google’s BERTSSRN Electronic Journal10.2139/ssrn.4614402Online publication date: 2023
    • (2023)Eligibility Mechanisms: Auctions Meet Information RetrievalProceedings of the ACM Web Conference 202310.1145/3543507.3583478(3541-3549)Online publication date: 30-Apr-2023
    • (2023) Feynman : Federated Learning-Based Advertising for Ecosystems-Oriented Mobile Apps Recommendation IEEE Transactions on Services Computing10.1109/TSC.2023.328593516:5(3361-3372)Online publication date: Sep-2023
    • (2021)Does More Context Help? Effects of Context Window and Application Source on Retrieval PerformanceACM Transactions on Information Systems10.1145/347405540:2(1-40)Online publication date: 27-Sep-2021
    • (2021)CHASEProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3481902(4352-4361)Online publication date: 26-Oct-2021
    • (2021)Web Object Ranking for Location-Based Web Object SearchAdvances in Smart Communication and Imaging Systems10.1007/978-981-15-9938-5_16(151-165)Online publication date: 14-Apr-2021
    • (2019)Personalized Online Spell Correction for Personal SearchThe World Wide Web Conference10.1145/3308558.3313706(2785-2791)Online publication date: 13-May-2019
    • (2019)AiAdsProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330782(1881-1890)Online publication date: 25-Jul-2019
    • (2019)MOBIUSProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330651(2509-2517)Online publication date: 25-Jul-2019
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media