Optimizing web search using social annotations

ABSTRACT

This paper explores the use of social annotations to improve websearch. Nowadays, many services, e.g. del.icio.us, have been developed for web users to organize and share their favorite webpages on line by using social annotations. We observe that the social annotations can benefit web search in two aspects: 1) the annotations are usually good summaries of corresponding webpages; 2) the count of annotations indicates the popularity of webpages. Two novel algorithms are proposed to incorporate the above information into page ranking: 1) SocialSimRank (SSR)calculates the similarity between social annotations and webqueries; 2) SocialPageRank (SPR) captures the popularity of webpages. Preliminary experimental results show that SSR can find the latent semantic association between queries and annotations, while SPR successfully measures the quality (popularity) of a webpage from the web users' perspective. We further evaluate the proposed methods empirically with 50 manually constructed queries and 3000 auto-generated queries on a dataset crawledfrom delicious. Experiments show that both SSR and SPRbenefit web search significantly.

REFERENCES

• 1: A. Hotho, R. Jaschke, C. Schmitz, and G. Stumme. Information Retrieval in Folksonomies: Search and Ranking. In: Proc. of ESWC 2006, pp. 411--426, 2006.
• 2: A. Mathes. Folksonomies -- Cooperative Classification and Communication through Shared Metadata. http://www.adammathes.com/academic/computer-mediatedcommunication/folksonomies.html, December 2004.
• 3: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 4: Delicious: http://del.icio.us
• 5: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, 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.1148177]
• 6: E. Quintarelli. Folksonomies: power to the people. Paper presented at the ISKO Italy-UniMIB meeting. http://www.iskoi.org/doc/folksonomies.htm, June 2005.
• 7: Frank McSherry, A uniform approach to accelerated PageRank computation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060829]
• 8: G. Golub, C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, 1989.
• 9: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 10: Gui-Rong Xue , Hua-Jun Zeng , Zheng Chen , Yong Yu , Wei-Ying Ma , WenSi Xi , WeiGuo Fan, Optimizing web search using web click-through data, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031192]
• 11: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 12: G. Smith. Atomiq: Folksonomy: social classification. http://atomiq.org/archives/2004/08/folksonomy_social_classification.html, Aug 3, 2004.
• 13: http://blog.del.icio.us/
• 14: http://www.marketingpilgrim.com/2006/01/winks-michaeltanne-discusses-future.html
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 16: 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]
• 17: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 18: Micah Dubinko , Ravi Kumar , Joseph Magnani , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, Visualizing tags over time, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135810]
• 19: Matthew Richardson , Amit Prakash , Eric Brill, Beyond PageRank: machine learning for static ranking, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135881]
• 20: Mark Sanderson, Retrieving with Good Sense, Information Retrieval, v.2 n.1, p.49-69, February 2000 [doi>10.1023/A:1009933700147]
• 21: Nick Craswell , David Hawking , Stephen Robertson, Effective site finding using link anchor information, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.250-257, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383999]
• 22: O. Dekel, C. Manning, and Y. Singer. Log-linear models for label-ranking. In: Advances in Neural Information Processing Systems (16). Cambridge, MA: MIT Press, 2003.
• 23: Pavel A. Dmitriev , Nadav Eiron , Marcus Fontoura , Eugene Shekita, Using annotations in enterprise search, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135900]
• 24: P. Merholz. Metadata for the Masses. October 19, 2004. http://www.adaptivepath.com/publications/essays/archives/000361.php
• 25: P. Mika Ontologies are us: a unified model of social networks and semantics. In: Proc. of ISWC 2005. pp. 522--536, Nov. 2005.
• 26: R. Herbrich, T. Graepel, and K. Obermayer. Support vector learning for ordinal regression. In: Proc. of the 9th International Conference on Artificial Neural Networks, pp. 97--102. 1999.
• 27: Scott A. Golder , Bernardo A. Huberman, Usage patterns of collaborative tagging systems, Journal of Information Science, v.32 n.2, p.198-208, April 2006 [doi>10.1177/0165551506062337]
• 28: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 29: S. E. Robertson, S. Walker, M. Hancock-Beaulieu, A. Gull, M. Lau. Okapi at TREC. In:Text REtrieval Conference, pp. 21--30, 1992.
• 30: T. Hammond, T. Hannay, B. Lund, and J. Scott. Social book marking tools (i) - a general review. D-Lib Magazine, 11(4), 2005.
• 31: Thomas Hofmann , Jan Puzicha, Statistical Models for Co-occurrence Data, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 32: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 33: T. V. Wal. Explaining and showing broad and narrow folksonomies. http://www.personalinfocloud.com/2005/02/ explaining_and_.html : February 21, 2005.
• 34: T. Westerveld., W. Kraaij., and D. Hiemstra, Retrieving Web Pages using Content, Links, URLs and Anchors, in: Proc. of TREC10, 2002.
• 35: WordNet: http://wordnet.princeton.edu/
• 36: Xian Wu , Lei Zhang , Yong Yu, Exploring social annotations for the semantic web, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135839]
• 37: Yunhua Hu , Guomao Xin , Ruihua Song , Guoping Hu , Shuming Shi , Yunbo Cao , Hang Li, Title extraction from bodies of HTML documents and its application to web page retrieval, 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.1076079]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Human Factors

Keywords:
evaluation, social annotation, social page rank, social similarity, web search