Personalized query expansion for the web

ABSTRACT

The inherent ambiguity of short keyword queries demands for enhanced methods for Web retrieval. In this paper we propose to improve such Web queries by expanding them with terms collected from each user's Personal Information Repository, thus implicitly personalizing the search output. We introduce five broad techniques for generating the additional query keywords by analyzing user data at increasing granularity levels, ranging from term and compound level analysis up to global co-occurrence statistics, as well as to using external thesauri. Our extensive empirical analysis under four different scenarios shows some of these approaches to perform very well, especially on ambiguous queries, producing a very strong increase in the quality of the output rankings. Subsequently, we move this personalized search framework one step further and propose to make the expansion process adaptive to various features of each query. A separate set of experiments indicates the adaptive algorithms to bring an additional statistically significant improvement over the best static expansion approach.

REFERENCES

• 1: James Allan , Hema Raghavan, Using part-of-speech patterns to reduce query ambiguity, 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.564430]
• 2: Peter G. Anick , Suresh Tipirneni, The paraphrase search assistant: terminological feedback for iterative information seeking, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.153-159, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312670]
• 3: David Carmel , Eitan Farchi , Yael Petruschka , Aya Soffer, Automatic query wefinement using lexical affinities with maximal information gain, 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.564427]
• 4: 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]
• 5: Chia-Hui Chang , Ching-Chi Hsu, Integrating query expansion and conceptual relevance feedback for personalized Web information retrieval, Proceedings of the seventh international conference on World Wide Web 7, p.621-623, April 1998, Brisbane, Australia
• 6: Paul-Alexandru Chirita , Claudiu S. Firan , Wolfgang Nejdl, Summarizing local context to personalize global web search, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183658]
• 7: 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]
• 8: Hang Cui , Ji-Rong Wen , Jian-Yun Nie , Wei-Ying Ma, Probabilistic query expansion using query logs, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511489]
• 9: Ted Dunning, Accurate methods for the statistics of surprise and coincidence, Computational Linguistics, v.19 n.1, March 1993
• 10: H. P. Edmundson, New Methods in Automatic Extracting, Journal of the ACM (JACM), v.16 n.2, p.264-285, April 1969 [doi>10.1145/321510.321519]
• 11: Efthimis N. Efthimiadis, User choices: a new yardstick for the evaluation of ranking algorithms for interactive query expansion, Information Processing and Management: an International Journal, v.31 n.4, p.605-620, July 1995 [doi>10.1016/0306-4573(95)00070-W]
• 12: Dániel Fogaras , Balázs Rácz, Scaling link-based similarity search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060839]
• 13: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 14: B. He and I. Ounis. Inferring query performance using pre-retrieval predictors. In Proc. of the 11th Intl. SPIRE Conf. on String Processing and Information Retrieval, 2004.
• 15: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 16: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 17: Myoung-Cheol Kim , Key-Sun Choi, A comparison of collocation-based similarity measures in query expansion, Information Processing and Management: an International Journal, v.35 n.1, p.19-30, Jan. 1999 [doi>10.1016/S0306-4573(98)00040-5]
• 18: Sang-Bum Kim , Hee-Cheol Seo , Hae-Chang Rim, Information retrieval using word senses: root sense tagging approach, 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.1009038]
• 19: 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]
• 20: Robert Krovetz , W. Bruce Croft, Lexical ambiguity and information retrieval, ACM Transactions on Information Systems (TOIS), v.10 n.2, p.115-141, April 1992 [doi>10.1145/146802.146810]
• 21: 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]
• 22: Shuang Liu , Fang Liu , Clement Yu , Weiyi Meng, An effective approach to document retrieval via utilizing WordNet and recognizing phrases, 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.1009039]
• 23: George A. Miller, WordNet: a lexical database for English, Communications of the ACM, v.38 n.11, p.39-41, Nov. 1995 [doi>10.1145/219717.219748]
• 24: Lan Nie , Brian D. Davison , Xiaoguang Qi, Topical link analysis for 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.1148189]
• 25: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Univ., 1998.
• 26: Feng Qiu , Junghoo Cho, Automatic identification of user interest for personalized search, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135883]
• 27: 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]
• 28: J. Rocchio. Relevance feedback in information retrieval. The Smart Retrieval System: Experiments in Automatic Document Processing, pages 313--323, 1971.
• 29: 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]
• 30: Tamás Sarlós , Adrás A. Benczúr , Károly Csalogány , Dániel Fogaras , Balázs Rácz, To randomize or not to randomize: space optimal summaries for hyperlink analysis, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135823]
• 31: Chirag Shah , W. Bruce Croft, Evaluating high accuracy retrieval techniques, 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.1008996]
• 32: Kazunari Sugiyama , Kenji Hatano , Masatoshi Yoshikawa, Adaptive web search based on user profile constructed without any effort from users, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988764]
• 33: D. Sullivan. The older you are, the more you want personalized search, 2004. http://searchenginewatch.com/searchday/article.php/3385131.
• 34: Jaime Teevan , Susan T. Dumais , Eric Horvitz, Personalizing search via automated analysis of interests and activities, 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.1076111]
• 35: Eugene Volokh, Personalization and privacy, Communications of the ACM, v.43 n.8, p.84-88, Aug. 2000 [doi>10.1145/345124.345155]
• 36: Ellen M. Voorhees, Query expansion using lexical-semantic relations, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.61-69, July 03-06, 1994, Dublin, Ireland
• 37: 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]
• 38: Shipeng Yu , Deng Cai , Ji-Rong Wen , Wei-Ying Ma, Improving pseudo-relevance feedback in web information retrieval using web page segmentation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775155]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
desktop profile, keyword co-occurrences, keyword extraction, personalized web search, query expansion