Questioning query expansion: an examination of behaviour and parameters

ABSTRACT

In information retrieval, queries can fail to find documents due to mismatch in terminology. Query expansion is a well-known technique addressing this problem, where additional query terms are automatically chosen from highly ranked documents, and it has been shown to be effective at improving query performance. However, current techniques for query expansion use fixed values for key parameters, determined by tuning on test collections. In this paper we show that these parameters may not be generally applicable, and more significantly that the assumption that the same parameter settings can be used for all queries is invalid. Using detailed experiments with two test collections, we demonstrate that new methods for choosing parameters must be found. However, our experiments also demonstrate that there is considerable further scope for improvement to effectiveness through better query expansion.

REFERENCES

• 1: Arampatzis, A. & van der Weide, T. (2001), "Document filtering as an adaptive and temporally-dependent process".
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 4: Bodo Billerbeck , Falk Scholer , Hugh E. Williams , Justin Zobel, Query expansion using associated queries, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956866]
• 5: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 6: Buckley, C., Salton, G., Allan, J. & Singhal, A (1994), Automatic query expansion using SMART: TREC 3, in "Text REtrieval Conference".
• 7: Claudio Carpineto , Renato de Mori , Giovanni Romano , Brigitte Bigi, An information-theoretic approach to automatic query expansion, ACM Transactions on Information Systems (TOIS), v.19 n.1, p.1-27, Jan. 2001 [doi>10.1145/366836.366860]
• 8: Steve Cronen-Townsend , Yun Zhou , W. Bruce Croft, Predicting query performance, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564429]
• 9: D. J. Foskett, Thesaurus, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 10: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 11: Donna Harman, Overview of the second text retrieval conference (TREC-2), Information Processing and Management: an International Journal, v.31 n.3, p.271-289, May-June 1995
• 12: Keiichiro Hoashi , Kazunori Matsumoto , Naomi Inoue , Kazuo Hashimoto, Query expansion method based on word contribution (poster abstract), Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.303-304, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312733]
• 13: In-Ho Kang , GilChang Kim, Query type classification for web document retrieval, 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.860449]
• 14: Marcin Kaszkiel , Justin Zobel, Effective ranking with arbitrary passages, Journal of the American Society for Information Science and Technology, v.52 n.4, p.344-364, Feb. 2001 [doi>10.1002/1532-2890(2000)9999:9999<::AID-ASI1075>3.3.CO;2-R]
• 15: K. L. Kwok, Higher precision for two-word queries, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564461]
• 16: Anton Leuski, Relevance and reinforcement in interactive browsing, Proceedings of the ninth international conference on Information and knowledge management, p.119-126, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354809]
• 17: Rila Mandala , Takenobu Tokunaga , Hozumi Tanaka, Combining multiple evidence from different types of thesaurus for query expansion, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.191-197, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312677]
• 18: Hiroko Mano , Yasushi Ogawa, Selecting expansion terms in automatic query expansion, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.390-391, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384032]
• 19: Page, L., Brin, S., Motwani, R. & Winograd, T. (1998), The pagerank citation ranking: Bringing order to the web, Technical report, Stanford Digital Library Technologies Project.
• 20: Yonggang Qiu , Hans-Peter Frei, Concept based query expansion, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.160-169, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160713]
• 21: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 22: Robertson, S. E. & Walker, S. (1999), Okapi/Keenbow at TREC-8, in "The Eighth Text REtrieval Conference (TREC-8)", NIST Special Publication 500-264, Gaithersburg, MD, pp. 151--161.
• 23: Robertson, S. E. & Walker, S. (2000), Microsoft Cambridge at TREC-9: Filtering Track, in "The Ninth Text RE-trieval Conference (TREC-9)", NIST Special Publication 500-249, Gaithersburg, MD, pp. 361--368.
• 24: Robertson, S. E., Walker, S., Hancock-Beaulieu, M., Gull, A. & Lau, M. (1992), Okapi at TREC, in "Text RETrieval Conference", pp. 21--30.
• 25: Rocchio, J. J. (1971), Relevance feedback in information retrieval, in E. Ide & G. Salton, eds, "The Smart Retrieval System --- Experiments in Automatic Document Processing", Prentice-Hall, Englewood, Cliffs, New Jersey, pp. 313--323.
• 26: Tetsuya Sakai , Stephen E. Robertson, Flexible pseudo-relevance feedback using optimization tables, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.396-397, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384035]
• 27: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 28: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 29: Falk Scholer , Hugh E. Williams, Query association for effective retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584846]
• 30: Candy Schwartz, Web search engines, Journal of the American Society for Information Science, v.49 n.11, p.973-982, Sept. 1998 [doi>10.1002/(SICI)1097-4571(1998)49:11<973::AID-ASI3>3.0.CO;2-Z]
• 31: K. Sparck Jones , S. Walker , S. E. Robertson, A probabilistic model of information retrieval: development and comparative experiments, Information Processing and Management: an International Journal, v.36 n.6, p.779-808, Nov.06.2000 [doi>10.1016/S0306-4573(00)00015-7]
• 32: Amanda Spink , Bernard J. Jansen , Dietmar Wolfram , Tefko Saracevic, From E-Sex to E-Commerce: Web Search Changes, Computer, v.35 n.3, p.107-109, March 2002 [doi>10.1109/2.989940]
• 33: Voorhees, E. M. & Harman, D. K. (1999), Overview of the Eighth Text REtrieval Conference (TREC-8), in E. M. Voorhees & D. K. Harman, eds, "The Eighth Text REtrieval Conference (TREC 8)", National Institute of Standards and Technology Special Publication 500-249, Gaithersburg, MD, pp. 1--23.
• 34: Voorhees, E. M. & Harman, D. K. (2000), Overview of the Ninth Text REtrieval Conference (TREC-9), in E. M. Voorhees & D. K. Harman, eds, "The Ninth Text REtrieval Conference (TREC 9)", National Institute of Standards and Technology Special Publication 500-249, Gaithersburg, MD, pp. 1--14.
• 35: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 36: Jinxi Xu , W. Bruce Croft, Query expansion using local and global document analysis, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243202]

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: Retrieval models

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
effectiveness, information retrieval, query expansion, search engines