Visualizing and communicating insights through maps offers an intuitive and familiar way to explore large-scale dynamic relational data. In this paper, we present VideoMap, which is a novel approach for presenting and interacting with relational video content by taking advantage of the map metaphor. VideoMap employs a metaphor to visualize video content by elements of a map with the aim of enabling exploration of video content as if reading a map. Video content is visualized in a hierarchal structure from a very large scale to a small scale of finely detailed representation. VideoMap recognizes a small set of sketch gestures for semantic zooming in and out, annotating the map, and automatically completing path navigation. To achieve this, VideoMap synthesizes map-derived visuals and binds them to the underlying data by operating the map with sketch interaction to facilitate interactive exploration. Extensive user studies were conducted to evaluate VideoMap, and the results demonstrated the effectiveness of VideoMap for facilitating the exploration and understanding of large video content.