Techniques for object re-identification based on temporal context. Embodiments extract, from a first image corresponding to a first camera device and a second image corresponding to a second camera device, a first plurality of patch descriptors and a second plurality of patch descriptors, respectively. A measure of visual similarity between the first image and the second image is computed, based on the first plurality of patch descriptors and the second plurality of patch descriptors. A temporal cost between the first image and the second image is computed, based on a first timestamp at which the first image was captured and a second timestamp at which the second image was captured. The measure of visual similarity and the temporal cost are combined into a single cost function, and embodiments determine whether the first image and the second image depict a common object, using the single cost function.