Query expansion using associated queries

ABSTRACT

Hundreds of millions of users each day use web search engines to meet their information needs. Advances in web search effectiveness are therefore perhaps the most significant public outcomes of IR research. Query expansion is one such method for improving the effectiveness of ranked retrieval by adding additional terms to a query. In previous approaches to query expansion, the additional terms are selected from highly ranked documents returned from an initial retrieval run. We propose a new method of obtaining expansion terms, based on selecting terms from past user queries that are associated with documents in the collection. Our scheme is effective for query expansion for web retrieval: our results show relative improvements over unexpanded full text retrieval of 26%--29%, and 18%--20% over an optimised, conventional expansion approach.

REFERENCES

• 1: Arvind Arasu , Junghoo Cho , Hector Garcia-Molina , Andreas Paepcke , Sriram Raghavan, Searching the Web, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.2-43, Aug. 2001 [doi>10.1145/383034.383035]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Peter Bailey , Nick Craswell , David Hawking, Engineering a multi-purpose test collection for web retrieval experiments, Information Processing and Management: an International Journal, v.39 n.6, p.853-871, November 2003 [doi>10.1016/S0306-4573(02)00084-5]
• 4: Bodo Billerbeck , Justin Zobel, When query expansion fails, 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.860514]
• 5: Buckley, C., Salton, G., Allan, J. & Singhal, A. (1994), Automatic query expansion using SMART: TREC 3, in D. Harman, ed., 'Overview of the Third Text REtrieval Conference (TREC-3)', NIST Special Publication 500-225, pp.69--80.
• 6: 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]
• 7: Nick Craswell , David Hawking , Stephen Robertson, Effective site finding using link anchor information, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.250-257, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383999]
• 8: Daniel, W. (1990), Applied Nonparametric Statistics, 2nd edn, PWS-KENT Publishing Company.
• 9: Larry Fitzpatrick , Mei Dent, Automatic feedback using past queries: social searching?, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.306-313, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 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: 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: Hawking, D. (2000), Overview of the TREC-9 web track, in 'The Ninth Text REtrieval Conference (TREC 9)', National Institute of Standards and Technology Special Publication 500-249, Washington, DC, pp.87--99.
• 13: Hawking, D. & Craswell, N. (2001), Overview of the TREC-2001 web track, in E. M. Voorhees & D. K. Harman, eds, 'The Tenth Text REtrieval Conference (TREC 2001)', National Institute of Standards and Technology Special Publication 500-250, Washington, DC, pp.61--67.
• 14: Adenike M. Lam-Adesina , Gareth J. F. Jones, Applying summarization techniques for term selection in relevance feedback, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.1-9, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383953]
• 15: 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]
• 16: 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]
• 17: Vijay V. Raghavan , Hayri Sever, On the reuse of past optimal queries, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.344-350, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215381]
• 18: Robertson, S. E. & Walker, S. (1999), Okapi/Keenbow at TREC-8, in E. M. Voorhees & D. K. Harman, eds, 'The Eighth Text REtrieval Conference (TREC-8)', NIST Special Publication 500-264, Gaithersburg, MD, pp.151--161.
• 19: Robertson, S. E. & Walker, S. (2000), Microsoft cambridge at trec-9: Filtering track, in E. M. Voorhees & D. K. Harman, eds, 'The Ninth Text REtrieval Conference (TREC-9)', NIST Special Publication 500-249, Gaithersburg, MD, pp.361--368.
• 20: Robertson, S. E., Walker, S., Hancock-Beaulieu, M., Gull, A. & Lau, M. (1992), Okapi at TREC, in D. K. Harman, ed., 'The First Text REtrieval Conference (TREC-1)', NIST Special Publication 500-207, Gaithersburg, MD, pp.21--30.
• 21: 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.
• 22: 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]
• 23: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 24: 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]
• 25: Scholer, F., Williams, H. & Turpin, A. (2003), Document surrogates for web search.(Manuscript in submission).
• 26: 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]
• 27: 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]
• 28: Amanda Spink , Dietmar Wolfram , Major B. J. Jansen , Tefko Saracevic, Searching the Web: the public and their queries, Journal of the American Society for Information Science and Technology, v.52 n.3, p.226-234, Feb. 1, 2001 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1591>3.3.CO;2-I]
• 29: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 30: Ellen M. Voorhees , Chris Buckley, The effect of topic set size on retrieval experiment error, 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.564432]
• 31: 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.
• 32: Voorhees, E. M. & Harman, D. K. (2001), Overview of TREC 2001, in E. M. Voorhees & D. K. Harman, eds, 'The Tenth Text REtrieval Conference (TREC 2001)', National Institute of Standards and Technology Special Publication 500-250, Gaithersburg, MD, pp.1--15.
• 33: 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
• 34: Justin Zobel, How reliable are the results of large-scale information retrieval experiments?, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.307-314, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291014]

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; Relevance feedback
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Experimentation, Performance

Keywords:
query association, query expansion, web search