The invention displays video search results in a form that makes it easy for users to determine which results are truly relevant. Each story returned as a search result is visualized as a collage of keyframes from the story's shots. The selected keyframes and their sizes depend on the corresponding shots' respective relevance. Shot relevance depends on the search retrieval score of the shot and, in some embodiments, also depends on the search retrieval score of the shot's parent story. Once areas have been determined, the keyframes are scaled and/or cropped to fit into the area. In one embodiment, users can mark one or more shots as being relevant to the search. In one embodiment, a timeline is created and displayed with one or more neighbor stories that are each part of the video and which are closest in time of creation to the selected story.