A large-scale evaluation and analysis of personalized search strategies

ABSTRACT

Although personalized search has been proposed for many years and many personalization strategies have been investigated, it is still unclear whether personalization is consistently effective on different queries for different users, and under different search contexts. In this paper, we study this problem and get some preliminary conclusions. We present a large-scale evaluation framework for personalized search based on query logs, and then evaluate five personalized search strategies (including two click-based and three profile-based ones) using 12-day MSN query logs. By analyzing the results, we reveal that personalized search has significant improvement over common web search on some queries but it also has little effect on other queries (e.g., queries with small click entropy). It even harms search accuracy under some situations. Furthermore, we show that straightforward click-based personalization strategies perform consistently and considerably well, while profile-based ones are unstable in our experiments. We also reveal that both long-term and short-term contexts are very important in improving search performance for profile-based personalized search strategies.

REFERENCES

• 1: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder, Hourly analysis of a very large topically categorized web query log, 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.1009048]
• 2: J. Boyan, D. Freitag, and T. Joachims. Evaluating retrieval performance using clickthrough data. In Proceedings of AAAI Workshop on Internet Based Information Systems, 1996.
• 3: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 4: John M. Carroll , Mary Beth Rosson, Paradox of the active user, Interfacing thought: cognitive aspects of human-computer interaction, MIT Press, Cambridge, MA, 1987
• 5: 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]
• 6: Paul Alexandru Chirita , Wolfgang Nejdl , Raluca Paiu , Christian Kohlschütter, Using ODP metadata to personalize search, 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.1076067]
• 7: S. Cronen-Townsend and W. B. Croft. Quantifying query ambiguity. In Proceedings of HLT '02, pages 94--98, 2002.
• 8: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 9: Paolo Ferragina , Antonio Gulli, A personalized search engine based on web-snippet hierarchical clustering, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062760]
• 10: 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]
• 11: Bernard J. Jansen , Amanda Spink , Judy Bateman , Tefko Saracevic, Real life information retrieval: a study of user queries on the Web, ACM SIGIR Forum, v.32 n.1, p.5-17, Spring 1998 [doi>10.1145/281250.281253]
• 12: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 13: J. C. Borda. Mémoire sur les élections au scrution. Histoire de l'Académie Royal des Sciences, 1781.
• 14: 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]
• 15: D. H. John S. Breese and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of UAI '98, pages 43--52, 1998.
• 16: 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]
• 17: Uichin Lee , Zhenyu Liu , Junghoo Cho, Automatic identification of user goals in Web search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060804]
• 18: Ying Li , Zijian Zheng , Honghua (Kathy) Dai, KDD CUP-2005 report: facing a great challenge, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.91-99, December 2005 [doi>10.1145/1117454.1117466]
• 19: Fang Liu , Clement Yu , Weiyi Meng, Personalized web search by mapping user queries to categories, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584884]
• 20: L. Page, S. Brin, R. Motwani,, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Computer Science Department, Stanford University, 1998.
• 21: James Pitkow , Hinrich Schütze , Todd Cass , Rob Cooley , Don Turnbull , Andy Edmonds , Eytan Adar , Thomas Breuel, Personalized search, Communications of the ACM, v.45 n.9, September 2002 [doi>10.1145/567498.567526]
• 22: Alexander Pretschner , Susan Gauch, Ontology Based Personalized Search, Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence, p.391, November 08-10, 1999
• 23: 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]
• 24: Dou Shen , Rong Pan , Jian-Tao Sun , Jeffrey Junfeng Pan , Kangheng Wu , Jie Yin , Qiang Yang, Q²C@UST: our winning solution to query classification in KDDCUP 2005, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.100-110, December 2005 [doi>10.1145/1117454.1117467]
• 25: Xuehua Shen , Bin Tan , ChengXiang Zhai, Context-sensitive information retrieval using implicit feedback, 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.1076045]
• 26: Xuehua Shen , Bin Tan , ChengXiang Zhai, Implicit user modeling for personalized search, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099747]
• 27: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 28: Micro Speretta , Susan Gauch, Personalized Search Based on User Search Histories, Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence, p.622-628, September 19-22, 2005 [doi>10.1109/WI.2005.114]
• 29: 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]
• 30: Jian-Tao Sun , Hua-Jun Zeng , Huan Liu , Yuchang Lu , Zheng Chen, CubeSVD: a novel approach to personalized Web search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060803]
• 31: Bin Tan , Xuehua Shen , ChengXiang Zhai, Mining long-term search history to improve search accuracy, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150493]
• 32: F. Tanudjaja , L. Mui, Persona: A Contextualized and Personalized Web Search, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 3, p.67, January 07-10, 2002
• 33: Jaime Teevan , Eytan Adar , Rosie Jones , Michael Potts, History repeats itself: repeat queries in Yahoo's logs, 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.1148326]
• 34: J. Teevan, S. T. Dumais, and E. Horvitz. Beyond the commons: Investigating the value of personalizing web search. In Proceedings of PIA '05, 2005.
• 35: 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]
• 36: Steve Wedig , Omid Madani, A large-scale analysis of query logs for assessing personalization opportunities, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150497]
• 37: Y. Xie and D. R. O'Hallaron. Locality in search engine queries and its implications for caching. In INFOCOM '02, 2002.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Experimentation, Human Factors, Theory

Keywords:
click-through, personalization, personalized search, query log, re-ranking