Methods, systems, and computer programs are presented for detecting near duplicates and partial matches of videos. One method includes an operation for receiving a video containing frames. For each frame, keypoints are determined within the frame. For each keypoint, a horizontal gradient vector is calculated based on a horizontal gradient at the keypoint and a vertical gradient vector is calculated based on a vertical gradient at the keypoint. The horizontal and vertical gradients are binary vectors. Further, a keypoint description is generated for each keypoint based on the horizontal gradient vector and the vertical gradient vector. Further, the frames are matched to frames of videos in a video library based on the keypoint descriptions of the keypoints in the frame in the videos in the video library. Further, a determination is made if the video has near duplicates in the video library based on the matching.