Embodiments presented herein describe techniques for generating a story graph using a collection of digital media, such as images and video. The story graph presents a structure for activities, events, and locales commonly occurring in sets of photographs taken by different individuals across a given location (e.g., a theme park, tourist attraction, convention, etc.). To build a story graph, streams from sets of digital media are generated. Each stream corresponds to media (e.g., images or video) taken in sequence at the location by an individual (or related group of individuals) over a period of time. For each stream, features from each media are extracted relative to the stream. Clusters of media are generated and are connected by directed edges. The connections indicate a path observed to have occurred in the streams from one cluster to another cluster.