Effective and efficient user interaction for long queries

ABSTRACT

Handling long queries can involve either pruning the query to retain only the important terms (reduction), or expanding the query to include related concepts (expansion). While automatic techniques to do so exist, roughly 25% performance improvements in terms of MAP have been realized in past work through interactive variants. We show that selectively reducing or expanding a query leads to an average improvement of 51% in MAP over the baseline for standard TREC test collections. We demonstrate how user interaction can be used to achieve this improvement. Most interaction techniques present users with a fixed number of options for all queries. We achieve improvements by interacting less with the user, i.e., we present techniques to identify the optimal number of options to present to users, resulting in an interface with an average of 70% fewer options to consider. Previous algorithms supporting interactive reduction and expansion are exponential in nature. To extend their utility to operational environments, we present techniques to make the complexity of the algorithms polynomial. We finally present an analysis of long queries that continue to exhibit poor performance in spite of our new techniques.

REFERENCES

• 1: Azzah Al-Maskari , Mark Sanderson , Paul Clough, The relationship between IR effectiveness measures and user satisfaction, 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.1277902]
• 2: J. Allan. The HARD Track Overview in TREC 2003. High Accuracy Retrieval from Documents. In TREC 12 Proceedings, 2003.
• 3: David Carmel , Elad Yom-Tov , Adam Darlow , Dan Pelleg, What makes a query difficult?, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148238]
• 4: Kenneth Ward Church , Patrick Hanks, Word association norms, mutual information, and lexicography, Proceedings of the 27th annual meeting on Association for Computational Linguistics, p.76-83, June 26-29, 1989, Vancouver, British Columbia, Canada [doi>10.3115/981623.981633]
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: 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]
• 7: Steve Cronen-Townsend , Yun Zhou , W. Bruce Croft, A framework for selective query expansion, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031220]
• 8: D. Harman, Towards interactive query expansion, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.321-331, May 1988, Grenoble, France [doi>10.1145/62437.62469]
• 9: D. Harman. How effective is suffixing? JASIS, 42(1):7--15, 1991.
• 10: Donna Harman , Chris Buckley, The NRRC reliable information access (RIA) workshop, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009104]
• 11: B. He and I. Ounis. Inferring query performance using pre-retrieval predictors. In The Eleventh Symposium on String Processing and Information Retrieval, 2004.
• 12: Scott Henninger , Nicholas J. Belkin, Interface issues and interaction strategies for information retrieval systems, Conference companion on Human factors in computing systems: common ground, p.352-353, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/257089.257364]
• 13: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 14: Diane Kelly , Vijay Deepak Dollu , Xin Fu, The loquacious user: a document-independent source of terms for query expansion, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076112]
• 15: Jürgen Koenemann , Nicholas J. Belkin, A case for interaction: a study of interactive information retrieval behavior and effectiveness, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.205-212, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238487]
• 16: Giridhar Kumaran , James Allan, Simple questions to improve pseudo-relevance feedback results, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148305]
• 17: G. Kumaran and J. Allan. A case for shorter queries, and helping users create them. In HLT-EMNLP Conference Proceedings, pages 220--227, Rochester, NY, 2007.
• 18: G. Kumaran and J. Allan. Adapting information retrieval systems to user queries. IP& M: Special Topic Issue on Adaptive Information Retrieval, In press, 2008.
• 19: Victor Lavrenko , W. Bruce Croft, Relevance based language models, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.120-127, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383972]
• 20: Mark Magennis , Cornelis J. van Rijsbergen, The potential and actual effectiveness of interactive query expansion, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.324-332, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 21: 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]
• 22: G. Salton , M. E. Lesk, Computer Evaluation of Indexing and Text Processing, Journal of the ACM (JACM), v.15 n.1, p.8-36, Jan. 1968 [doi>10.1145/321439.321441]
• 23: Mark D. Smucker , James Allan, Find-similar: similarity browsing as a search tool, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148250]
• 24: T. Strohman, D. Metzler, H. Turtle, and W. B. Croft. Indri: A language model-based search engine for complex queries. In International Conference on Intelligence Analysis, 2005.
• 25: Sergei Vassilvitskii , Eric Brill, Using web-graph distance for relevance feedback in web search, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148199]
• 26: Ellen M. Voorhees, The TREC 2005 robust track, ACM SIGIR Forum, v.40 n.1, June 2006 [doi>10.1145/1147197.1147205]
• 27: E. M. Voorhees and D. Harman. Overview of the fifth text retrieval conference (TREC 5). In TREC 5 Proceedings, 1996.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
interactive retrieval efficiency, query analysis, query expansion, query reduction, user interaction