Automatic video tagging using content redundancy

ABSTRACT

The analysis of the leading social video sharing platform YouTube reveals a high amount of redundancy, in the form of videos with overlapping or duplicated content. In this paper, we show that this redundancy can provide useful information about connections between videos. We reveal these links using robust content-based video analysis techniques and exploit them for generating new tag assignments. To this end, we propose different tag propagation methods for automatically obtaining richer video annotations. Our techniques provide the user with additional information about videos, and lead to enhanced feature representations for applications such as automatic data organization and search. Experiments on video clustering and classification as well as a user evaluation demonstrate the viability of our approach.

REFERENCES

• 1: James Allan , Ron Papka , Victor Lavrenko, On-line new event detection and tracking, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.37-45, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290954]
• 2: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001
• 3: Meeyoung Cha , Haewoon Kwak , Pablo Rodriguez , Yong-Yeol Ahn , Sue Moon, I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298309]
• 4: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 5: X. Cheng, C. Dale, and J. Liu. Understanding the characteristics of internet short video sharing: Youtube as a case study, Technical Report arXiv:0707.3670v1 {cs.NI}, Cornell University, arXiv e-prints, July 2007.
• 6: Nick Craswell , Martin Szummer, Random walks on the click graph, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277784]
• 7: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 8: N. Shivakumar and H. Garcia-Molina. Scam: A copy detection mechanism for digital documents. In Proceedings of the Second Annual Conference on the Theory and Practice of Digital Libraries. June 1995.
• 9: Phillipa Gill , Martin Arlitt , Zongpeng Li , Anirban Mahanti, Youtube traffic characterization: a view from the edge, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298310]
• 10: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 11: J.S. Hare, P.H. Lewis, P.G.B. Enser, and C.J. Sandom. Mind the gap: another look at the problem of the semantic gap in image retrieval. Multimedia Content Analysis, Management, and Retrieval 2006, 6073(1), 2006.
• 12: A. Hotho, R. Jäschke, C. Schmitz, and G. Stumme. Information Retrieval in Folksonomies: Search and Ranking. In The Semantic Web: Research and Applications, volume 4011 of LNAI, pages 411--426, Heidelberg, 2006. Springer.
• 13: Scott Huffman , April Lehman , Alexei Stolboushkin , Howard Wong-Toi , Fan Yang , Hein Roehrig, Multiple-signal duplicate detection for search evaluation, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277782]
• 14: Yushi Jing , Shumeet Baluja, Pagerank for product image search, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367540]
• 15: A. Joly, O. Buisson, and C. Frelicot. Content-based copy retrieval using distortion-based probabilistic similarity search. Multimedia, IEEE Transactions on, 9(2):293--306, 2007.
• 16: Yan Ke , Rahul Sukthankar , Larry Huston, An efficient parts-based near-duplicate and sub-image retrieval system, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027729]
• 17: 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]
• 18: R. Likert. A technique for the measurement of attitudes. Archives of Psychology, 22(140):1--55, 1932.
• 19: L. Liu, W. Lai, X.-S. Hua, and S.-Q. Yang. Video histogram: A novel video signature for efficient web video duplicate detection. Advances in Multimedia Modeling, pages 94--103, 2006.
• 20: Gurmeet Singh Manku , Arvind Jain , Anish Das Sarma, Detecting near-duplicates for web crawling, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242592]
• 21: 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.
• 22: Jose San Pedro, Fobs: an open source object-oriented library for accessing multimedia content, Proceeding of the 16th ACM international conference on Multimedia, October 26-31, 2008, Vancouver, British Columbia, Canada [doi>10.1145/1459359.1459580]
• 23: Jose San Pedro , Sergio Dominguez, Network-aware identification of video clip fragments, Proceedings of the 6th ACM international conference on Image and video retrieval, p.317-324, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282329]
• 24: Nicola Stokes , Joe Carthy, Combining semantic and syntactic document classifiers to improve first story detection, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.424-425, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384068]
• 25: B. Szekely and E. Torres. Ranking bookmarks and bistros: Intelligent community and folksonomy development. In http://torrez.us/archives/2005/07/13/tagrank.pdf (unpublished), 2005.
• 26: Stijn Dongen, A cluster algorithm for graphs, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2000
• 27: Xiao Wu , Alexander G. Hauptmann , Chong-Wah Ngo, Practical elimination of near-duplicates from web video search, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291280]
• 28: Hui Yang , Jamie Callan, Near-duplicate detection by instance-level constrained clustering, 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.1148243]
• 29: Benyu Zhang , Hua Li , Yi Liu , Lei Ji , Wensi Xi , Weiguo Fan , Zheng Chen , Wei-Ying Ma, Improving web search results using affinity graph, 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.1076120]
• 30: Yi Zhang , Jamie Callan , Thomas Minka, Novelty and redundancy detection in adaptive filtering, 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.564393]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

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

General Terms:
Algorithms

Keywords:
automatic tagging, content-based links, data organization, neighbor-based tagging, tag propagation, video duplicates