Much previous work in video fingerprinting has focused on robustness and security issues, but the compactness requirement, i.e., the hash should be of a short length with acceptable robustness and discriminability, continues to be a significant practical challenge. In this paper, we propose a video fingerprinting method with explicit attention on compactness. First, we develop a new graphical representation of the video which reduces temporal redundancies and makes robust feature extraction much more economical. Second, a randomized adaptive quantizer is proposed to further decrease the final hash length while maintaining acceptable detection performance in terms of receiver operating characteristics (ROCs). Experimental results reveal that the proposed method offers a more favorable robustness versus discriminability tradeoff over the state of the art particularly when the bit budget of the video fingerprint is low.