In this paper, we present a novel video fingerprinting algorithm which leverages the concept of perceptual similarity between different video sequences. Inspired by the popular structural similarity (SSIM) index, we quantify the perceptual similarity between different video sequences by proposing a perceptual distance metric (PDM) which is utilized in the matching stage of our proposed video fingerprinting algorithm. PDM requires very simple features, viz., block means and therefore has extremely low complexity in both the feature extraction part, as well as during the matching stage. We also show how to use an order statistic in the proposed distance measure to improve the system performance for localized block-based artifacts such as the logo artifact. Simulation results for the proposed fingerprinting algorithm show significant gains over other video fingerprinting techniques on different video datasets for numerous heavy video artifacts.