Web video topic discovery and tracking via bipartite graph reinforcement model

ABSTRACT

Automatic topic discovery and tracking on web-shared videos can greatly benefit both web service providers and end users. Most of current solutions of topic detection and tracking were done on news and cannot be directly applied on web videos, because the semantic information of web videos is much less than that of news videos. In this paper, we propose a bipartite graph model to address this issue. The bipartite graph represents the correlation between web videos and their keywords, and automatic topic discovery is achieved through two steps - coarse topic filtering and fine topic re-ranking. First, a weight-updating co-clustering algorithm is employed to filter out topic candidates at a coarse level. Then the videos on each topic are re-ranked by analyzing the link structures of the corresponding bipartite graph. After the topics are discovered, the interesting ones can also be tracked over a period of time using the same bipartite graph model. The key is to propagate the relevant scores and keywords from the videos of interests to other relevant ones through the bipartite graph links. Experimental results on real web videos from YouKu, a YouTube counterpart in China, demonstrate the effectiveness of the proposed methods. We report very promising results.

REFERENCES

• 1: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 2: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 3: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 4: Hsu, W. H. and Chang, S.-F., Topic Tracking across Broadcast News Videos with Visual Duplicates and Semantic Concepts, in Proc. Int'l Conf. Image Processing (ICIP), IEEE Press, 2006, pp. 141--144.
• 5: Winston H. Hsu , Lyndon S. Kennedy , Shih-Fu Chang, Video search reranking through random walk over document-level context graph, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291446]
• 6: 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]
• 7: http://www.youtube.com
• 8: http://mashable.com/2006/07/17/youtube-hits-1-million-videos-per-day/
• 9: http://www.youku.com
• 10: http://www.tudou.com
• 11: http://www.6room.com
• 12: http://www.nlp.org.cn/
• 13: http://www.alexa.com/data/details/traffic_details?url=youku.com
• 14: Ide, I., Mo, H., Katayama, N. and S. Satoh, Topic Threading for Structuring a Large-Scale News Video Archive, International Conference on Image and Video Retrieval, 2004.
• 15: John R. Kender , Milind R. Naphade, Visual Concepts for News Story Tracking: Analyzing and Exploiting the NIST TRECVID Video Annotation Experiment, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.1174-1181, June 20-26, 2005 [doi>10.1109/CVPR.2005.371]
• 16: 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]
• 17: LDC, TDT3 evaluation specification version 2.7, 1999.
• 18: Victor Lavrenko , James Allan , Edward DeGuzman , Daniel LaFlamme , Veera Pollard , Stephen Thomas, Relevance models for topic detection and tracking, Proceedings of the second international conference on Human Language Technology Research, March 24-27, 2002, San Diego, California
• 19: Leah S. Larkey , Fangfang Feng , Margaret Connell , Victor Lavrenko, Language-specific models in multilingual topic tracking, 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.1009061]
• 20: Amy N. Langville , Carl D. Meyer, A Survey of Eigenvector Methods for Web Information Retrieval, SIAM Review, v.47 n.1, p.135-161, 2005 [doi>10.1137/S0036144503424786]
• 21: Tim Leek , Richard Schwartz , Srinivasa Sista, Probabilistic approaches to topic detection and tracking, Topic detection and tracking: event-based information organization, Kluwer Academic Publishers, Norwell, MA, 2002
• 22: Douglas William Oard , Nicholas Declaris, Adaptive vector space text filtering for monolingual and cross-language application, University of Maryland at College Park, College Park, MD, 1996
• 23: Page, L., Brin, S., Motwani, R., and Winograd, T. The Pagerank Citation Ranking: Bringing Order to the web. Technical report, Stanford University, Stanford, CA, 1998.
• 24: STEAMING MEDIA WORLD, Jan, 2007 http://www.lmtw.com/
• 25: Yiming Yang , Jaime G. Carbonell , Ralf D. Brown , Thomas Pierce , Brian T. Archibald , Xin Liu, Learning Approaches for Detecting and Tracking News Events, IEEE Intelligent Systems, v.14 n.4, p.32-43, July 1999 [doi>10.1109/5254.784083]
• 26: Yun Zhai , Mubarak Shah, Tracking news stories across different sources, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101152]

INDEX TERMS

Primary 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

Keywords:
bipartite graph model, co-clustering, reinforcement, topic discovery, topic tracking, web videos