Mining near-duplicate graph for cluster-based reranking of web video search results

Abstract

Recently, video search reranking has been an effective mechanism to improve the initial text-based ranking list by incorporating visual consistency among the result videos. While existing methods attempt to rerank all the individual result videos, they suffer from several drawbacks. In this article, we propose a new video reranking paradigm called cluster-based video reranking (CVR). The idea is to first construct a video near-duplicate graph representing the visual similarity relationship among videos, followed by identifying the near-duplicate clusters from the video near-duplicate graph, then ranking the obtained near-duplicate clusters based on cluster properties and intercluster links, and finally for each ranked cluster, a representative video is selected and returned. Compared to existing methods, the new CVR ranks clusters and exhibits several advantages, including superior reranking by utilizing more reliable cluster properties, fast reranking on a small number of clusters, diverse and representative results. Particularly, we formulate the near-duplicate cluster identification as a novel maximally cohesive subgraph mining problem. By leveraging the designed cluster scoring properties indicating the cluster's importance and quality, random walk is applied over the near-duplicate cluster graph to rank clusters. An extensive evaluation study proves the novelty and superiority of our proposals over existing methods.

References

1. Bonchi, F. and Lucchese, C. 2005. Pushing tougher constraints in frequent pattern mining. In Proceedings of the Pacific-Asia Conference on Knowledge Discover and Data Mining (PAKDD). 114--124.
2. Carbonell, J. G. and Goldstein, J. 1998. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proceedings of the ACM Special Interest Group on Information Retrieval (SIGIR). 335--336.
3. Chakrabarti, D. and Faloutsos, C. 2006. Graph mining: Laws, generators, and algorithms. ACM Comput. Surv. 38, 1.
4. Cherubini, M., de Oliveira, R., and Oliver, N. 2009. Understanding near-duplicate videos: a user-centric approach. In Proceedings of the ACM Multimedia Conference. 35--44.
5. Frey, B. J. and Dueck, D. 2007. Clustering by passing messages between data points. Science 315, 972--976.
6. Hsu, W., Kennedy, L., and Chang, S.-F. 2006. Video search reranking via information bottleneck principle. In Proceedings of the ACM Multimedia Conference. 35--44.
7. Hsu, W., Kennedy, L., and Chang, S. F. 2007. Video search reranking through random walk over document-level context graph. In Proceedings of the ACM Multimedia Conference. 971--980.
8. Huang, Z., Shen, H. T., Shao, J., Zhou, X., and Cui, B. 2009. Bounded coordinate system indexing for real-time video clip search. ACM Trans. Inform. Syst. 27, 3.
9. Law-To, J., Chen, L., Joly, A., Laptev, Y., Buisson, O., Gouet, V., Boujemaa, N., and Stentiford, F. 2007. Video copy detection: a comparative study. In Proceedings of the ACM International Conference on Image and Video Retrieval (CIVR). 371--378.
10. Liu, J., Lai, W., Hua, X.-S., Huang, Y., and Li, S. 2007. Video search re-ranking via multi-graph propagation. In Proceedings of the ACM Multimedia Conference. 208--217.
11. Liu, Y., Mei, T., Hua, X.-S., Tang, J., Wu, X., and Li, S. 2008. Learning to video search rerank via pseudo preference feedback. In Proceedings of the International Conference on Multimedia & Expo (ICME). 297--300.
12. Moser, F., Colak, R., Rafiey, A., and Ester, M. 2009. Mining cohesive patterns from graphs with feature vectors. In Proceedings of the Siom Conference on Data Mining (SDM). 593--604.
13. Ngo, C.-W., Zhao, W., and Jiang, Y.-G. 2006. Fast tracking of near-duplicate keyframes in broadcast domain with transitivity propagation. In Proceedings of the ACM Multimedia Conference. 845--854.
14. Poullot, S., Crucianu, M., and Buisson, O. 2008. Scalable mining of large video databases using copy detection. In Proceedings of the ACM Multimedia Conference. 61--70.
15. Shen, H. T., Zhou, X., Huang, Z., and Shao, J. 2007a. Statistical summarization of content features for fast near-duplicate video detection. In Proceedings of the ACM Multimedia Conference. 164--165.
16. Shen, H. T., Zhou, X., Huang, Z., Shao, J., and Zhou, E. 2007b. Uqlips: A real-time near-duplicate video clip detection system. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 1374--1377.
17. Shi, J. and Malik, J. 2000. Normalized cuts and image segmentation. IEEE Trans. Patt. Anal. Mach. Intell. 22, 8, 888--905.
18. Tan, H.-K., Ngo, C.-W., Hong, R., and Chua, T.-S. 2009. Scalable detection of partial near-duplicate videos by visual-temporal consistency. In Proceedings of the ACM Multimedia Conference. 145--154.
19. Tan, H.-K., Ngo, C.-W., and Wu, X. 2008. Modeling video hyperlinks with hypergraph for Web video reranking. In Proceedings of the ACM Multimedia Conference. 659--662.
20. Tian, X., Yang, L., Wang, J., Yang, Y., Wu, X., and Hua, X.-S. 2008. Bayesian video search reranking. In Proceedings of the ACM Multimedia Conference. 131--140.
21. Wang, N., Parthasarathy, S., Tan, K.-L., and Tung, A. K. H. 2008. CSV: visualizing and mining cohesive subgraphs. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 445--458.
22. Wu, X., Hauptmann, A. G., and Ngo, C. W. 2007. Practical elimination of near-duplicates from Web video search. In Proceedings of the ACM Multimedia Conference. 218--227.
23. Yan, R., Hauptmann, A. G., and Jin, R. 2003. Multimedia search with pseudo-relevance feedback. In Proceedings of the ACM International Conference on Image and Video Retrieval (CIVR). 238--247.
24. Yan, Y., Ooi, B. C., and Zhou, A. 2008. Continuous content-based copy detection over streaming videos. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 853--862.
25. Zhao, W. and Ngo, C.-W. 2009. Scale-rotation invariant pattern entropy for keypoint-based near-duplicate detection. IEEE Trans. Image Process. 18, 2, 412--423.
26. Zhu, J., Hoi, S. C. H., Lyu, M. R., and Yan, S. 2008. Near-duplicate keyframe retrieval by nonrigid image matching. In Proceedings of the ACM Multimedia Conference. 41--50.
27. Zobel, J. and Hoad, T. C. 2006. Detection of video sequences using compact signatures. ACM Trans. Inform. Syst. 24, 1, 1--50.

Index Terms

• Information systems

  • Information retrieval

    • Information retrieval query processing

    • Retrieval models and ranking