Have you ever tried to search for videos on tigers in the jungle but found the first 20 results were videos about Tiger Woods? The authors of this paper have identified a relevant problem when they suggest that the rapid growth of multimedia search--particularly video--requires improved differentiation of the videos returned from a search. The authors suggest video search results clustering as a solution, and propose clustering based on both video content and text-based contextual information.

The results shown in this paper are impressive in comparison to the typical search result on YouTube, which provides no differentiation. For example, a search for “Sting” provides at least three clusters: musician, movie, and wrestler.

The unique contribution that these authors have made is that they rely on context information in addition to video content. To accomplish the video search results clustering, the authors use two algorithms: normalized cuts and affinity propagation. The normalized cuts algorithm provides a weighted graph where the nodes are videos and the edges represent what is similar in the videos. It uses recursion to identify partitions. Affinity propagation solves a limitation of normalized cuts by automatically determining the number of clusters (as opposed to the user entering the number of clusters).

It is clear that the details of this paper are for professional programmers and others who are involved in creating search results applications. However, even the general reader can identify with the need for improved video search results, and will be interested to know that this type of research is in progress.