A personalized search engine based on web-snippet hierarchical clustering

ABSTRACT

In this paper we propose a hierarchical clustering engine, called snaket, that is able to organize on-the-fly the search results drawn from 16 commodity search engines into a hierarchy of labeled folders. The hierarchy offers a complementary view to the flat-ranked list of results returned by current search engines. Users can navigate through the hierarchy driven by their search needs. This is especially useful for informative, polysemous and poor queries.SnakeT is the first complete and open-source system in the literature that offers both hierarchical clustering and folder labeling with variable-length sentences. We extensively test SnakeT against all available web-snippet clustering engines, and show that it achieves efficiency and efficacy performance close to the best known engine Vivisimo.com.Recently, personalized search engines have been introduced with the aim of improving search results by focusing on the users, rather than on their submitted queries. We show how to plug SnakeT on top of any (un-personalized) search engine in order to obtain a form of personalization that is fully adaptive, privacy preserving, scalable, and non intrusive for underlying search engines.

REFERENCES

• 1: http://labs.google.com/personalized.
• 2: http://mysearch.yahoo.com/.
• 3: G. Attardi, A. Gulli, and F. Sebastiani. Theseus: categorization by context. In WWW8, 1999.
• 4: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Proceedings of the seventh international conference on World Wide Web 7, p.379-388, April 1998, Brisbane, Australia
• 5: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 6: Claudio Carpineto , Giovanni Romano, Concept Data Analysis: Theory and Applications, John Wiley & Sons, 2004
• 7: Hao Chen , Susan Dumais, Bringing order to the Web: automatically categorizing search results, Proceedings of the SIGCHI conference on Human factors in computing systems, p.145-152, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332418]
• 8: P. A. Chirita, D. Olmedilla, and W. Nejdl. PROS: A personalized ranking platform for web search. In Int. Conf. on Adaptive Hypermedia and Web-based Syst., 2004.
• 9: SnakeT Dataset. http://roquefort.di.unipi.it/gulli/listAllowed/testSnakeT/.
• 10: B. Fung, K. Wang, and M. Ester. Large hierarchical document clustering using frequent itemsets. In SDM03.
• 11: F. Giannotti, M. Nanni, and D. Pedreschi. Webcat: Automatic categorization of web search results. In SEBD03.
• 12: Johannes Grabmeier , Andreas Rudolph, Techniques of Cluster Algorithms in Data Mining, Data Mining and Knowledge Discovery, v.6 n.4, p.303-360, October 2002 [doi>10.1023/A:1016308404627]
• 13: Maria Halkidi , Yannis Batistakis , Michalis Vazirgiannis, On Clustering Validation Techniques, Journal of Intelligent Information Systems, v.17 n.2-3, p.107-145, December 2001 [doi>10.1023/A:1012801612483]
• 14: 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]
• 15: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 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: Z. Jiang, A. Joshi, R. Krishnapuram, and L. Yi. Retriever: Improving web search engine results using clustering. In Managing Business with Electronic Commerce 02.
• 18: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 19: Krishna Kummamuru , Rohit Lotlikar , Shourya Roy , Karan Singal , Raghu Krishnapuram, A hierarchical monothetic document clustering algorithm for summarization and browsing search results, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988762]
• 20: Dawn J. Lawrie , W. Bruce Croft, Language models for hierarchical summarization, 2003
• 21: Dawn J. Lawrie , W. Bruce Croft, Generating hierarchical summaries for web searches, 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.860549]
• 22: Y. S. Maarek, R. Fagin, I. Z. Ben-Shaul, and D. Pelleg. Ephemeral document clustering for web applications. Technical Report RJ 10186, IBM Research, 2000.
• 23: M. Meila. Comparing clusterings. Technical Report 418, University of Washington, 2002.
• 24: Javed Mostafa. Seeking better web searches. Scientific American, February 2005.
• 25: S. Osinski and D. Weiss. Conceptual clustering using lingo algorithm: Evaluation on open directory project data. In IIPWM04, 2004.
• 26: SnakeTTest Results. http://roquefort.di.unipi.it/gulli/listAllowed/testing/.
• 27: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 28: http://www.searchenginelowdown.com/2004/10/web-20-exclusive-demons%tration-of.html.
• 29: http://www.betanews.com/article/Microsoft_Tests_Search_Clustering/%1106319504.
• 30: Yitong Wang , Masaru Kitsuregawa, On Combining Link and Contents Information for Web Page Clustering, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.902-913, September 02-06, 2002
• 31: D. Weiss and J. Stefanowski. Web search results clustering in polish: Experimental evaluation of carrot. In IIS03.
• 32: Y. Wu and X. Chen. Extracting features from web search returned hits for hierarchical classification. In IKE03.
• 33: Oren Zamir , Oren Etzioni, Grouper: a dynamic clustering interface to Web search results, Proceeding of the eighth international conference on World Wide Web, p.1361-1374, May 1999, Toronto, Canada
• 34: Hua-Jun Zeng , Qi-Cai He , Zheng Chen , Wei-Ying Ma , Jinwen Ma, Learning to cluster web search results, 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.1009030]
• 35: D. Zhang and Y. Dong. Semantic, hierarchical, online clustering of web search results. In WIDM01

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.5 On-line Information Services

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Keywords:
information extraction, new search applications and interfaces, personalized web ranking, search engines, web snippets clustering