Generating query substitutions

ABSTRACT

We introduce the notion of query substitution, that is, generating a new query to replace a user's original search query. Our technique uses modifications based on typical substitutions web searchers make to their queries. In this way the new query is strongly related to the original query, containing terms closely related to all of the original terms. This contrasts with query expansion through pseudo-relevance feedback, which is costly and can lead to query drift. This also contrasts with query relaxation through boolean or TFIDF retrieval, which reduces the specificity of the query. We define a scale for evaluating query substitution, and show that our method performs well at generating new queries related to the original queries. We build a model for selecting between candidates, by using a number of features relating the query-candidate pair, and by fitting the model to human judgments of relevance of query suggestions. This further improves the quality of the candidates generated. Experiments show that our techniques significantly increase coverage and effectiveness in the setting of sponsored search.

REFERENCES

• 1: Peter Anick, Using terminological feedback for web search refinement: a log-based study, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860453]
• 2: Paul N. Bennett, Using asymmetric distributions to improve text classifier probability estimates, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860457]
• 3: C.-C. Chang and C.-J. Lin. LIBSVM : A Library for Support Vector Machines, 2001. Software available at http://www.csie.ntu.edu.tw/ cjlin/libsvm.
• 4: S. Cucerzan and E. Brill. Spelling correction as an iterative process that exploits the collective knowledge of web users. In Proceedings of EMNLP 2004, pages 293--300, 2004.
• 5: 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.
• 6: L. Dumbgen. Pair-adjacent violators (PAV), available at http://www.math.mu-luebeck.de/workers/duembgen/software/software.html. In Statistical Software (MATLAB), 2000.
• 7: Ted Dunning, Accurate methods for the statistics of surprise and coincidence, Computational Linguistics, v.19 n.1, March 1993
• 8: D. C. Fain and J. O. Pedersen. Sponsored search. In Bulletin of the American Society for Information Science and Technology, 2005.
• 9: C. Fellbaum. WordNet: An Electronic Lexical Database. The MIT Press, 1998.
• 10: George W. Furnas, Experience with an adaptive indexing scheme, Proceedings of the SIGCHI conference on Human factors in computing systems, p.131-135, April 1985, San Francisco, California, United States
• 11: Rosie Jones , Daniel C. Fain, Query word deletion prediction, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860538]
• 12: Reiner Kraft , Jason Zien, Mining anchor text for query refinement, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988763]
• 13: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 14: J. C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In A. Smola, P. Bartlett, B. Schlkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 61--74. MIT Press, 1999.
• 15: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081899]
• 16: K. M. Risvik, T. Mikolajewski, and P. Boros. Query segmentation for web search. In Poster Session in The Twelfth International World Wide Web Conference, 2003.
• 17: Ian Ruthven, Re-examining the potential effectiveness of interactive query expansion, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860475]
• 18: A. Spink, B. J. Jansen, and H. C. Ozmultu. Use of query reformulation and relevance feedback by Excite users. Internet Research: Electronic Networking Applications and Policy, 10(4):317--328, 2000.
• 19: Egidio Terra , Charles L.A. Clarke, Scoring missing terms in information retrieval tasks, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031182]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Retrieval models

General Terms:
Algorithms, Experimentation

Keywords:
paraphrasing, query rewriting, query substitution, sponsored search