Efficient interactive query expansion with complete search

ABSTRACT

We present an efficient realization of the following interactive search engine feature: as the user is typing the query, words that are related to the last query word and that would lead to good hits are suggested, as well as selected such hits. The realization has three parts: (i) building clusters of related terms, (ii) adding this information as artificial words to the index such that (iii) the described feature reduces to an instance of prefix search and completion. An efficient solution for the latter is provided by the CompleteSearch engine, with which we have integrated the proposed feature. For building the clusters of related terms we propose a variant of latent semantic indexing that, unlike standard approaches, is completely transparent to the user. By experiments on two large test-collections, we demonstrate that the feature is provided at only a slight increase in query processing time and index size.

REFERENCES

• 1: Holger Bast , Debapriyo Majumdar, Why spectral retrieval works, 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.1076040]
• 2: Holger Bast , Ingmar Weber, Type less, find more: fast autocompletion search with a succinct index, 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.1148234]
• 3: Billerbeck, B. Efficient Query Expansion. PhD thesis, RMIT University, 2005.
• 4: Thorsten Brants, TnT: a statistical part-of-speech tagger, Proceedings of the sixth conference on Applied natural language processing, p.224-231, April 29-May 04, 2000, Seattle, Washington [doi>10.3115/974147.974178]
• 5: Deerwester, S. C., Dumais, S. T., Landauer, T. K., Furnas, G. W., and Harshman, R. A. Indexing by latent semantic analysis. JASIS 41, 6 (1990), 391--407.
• 6: Fellbaum, C., Ed. WordNet: An Electronic Lexical Database. MIT Press, 1998.
• 7: Bruno M. Fonseca , Paulo Golgher , Bruno Pôssas , Berthier Ribeiro-Neto , Nivio Ziviani, Concept-based interactive query expansion, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099726]
• 8: Porter, M. F. An algorithm for suffix stripping. Program 14, 3 (1980), 130--137.
• 9: 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]
• 10: Martin Theobald , Ralf Schenkel , Gerhard Weikum, Efficient and self-tuning incremental query expansion for top-k query processing, 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.1076077]
• 11: van Dongen, S. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, 2000. http://micans.org/mcl.
• 12: Voorhees, E. Overview of the Trec 2004 Robust retrieval track. In TREC (2004).

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.1 Content Analysis and Indexing
          Subjects: Indexing methods; Thesauruses
      H.3.3 Information Search and Retrieval
          Subjects: Search process
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

General Terms:
Design, Experimentation, Human Factors, Performance

Keywords:
index building, interactive, query expansion, synsets, wikipedia, wordnet