A novel robust video hashing scheme is proposed in thispaper. Unlike most existing robust video hashing algorithms, theproposed video hash is generated based on the motion vectorsinstead of the image textures in the video stream. Therefore,neither full decoding of the video stream nor complex computationof pixel values is required. Based on analysis of motion vectorproperties regarding their suitability for robust hashing, animproved feature extraction mechanism is proposed and severaloptimization mechanisms are introduced in order to achieve betterrobustness and discriminability. The proposed hashing scheme isevaluated by a large and modern video data set and theexperimental results demonstrate the excellent performance of theproposed hashing algorithm, which is comparable or even betterthan the complicated texture-based approaches.