Various technologies described herein pertain to creation of an output hyper-lapse video from an input video. Values indicative of overlaps between pairs of frames in the input video are computed. A value indicative of an overlap between a pair of frames can be computed based on a sparse set of points from each of the frames in the pair. Moreover, a subset of the frames from the input video are selected based on the values of the overlaps between the pairs of the frames in the input video and a target frame speed-up rate. Further, the output hyper-lapse video is generated based on the subset of the frames. The output hyper-lapse video can be generated without a remainder of the frames of the input video other than the subset of the frames.