In this paper, we propose a new algorithm to find video clips with different temporal durations and some spatial variations. We adopt a longest common sub-sequence (LCS) matching technique for measuring the temporal similarity between video clips. Based on the measure we propose 3 techniques to improve the retrieval effectiveness. First, we use a few coefficients in the low frequency region of DCT block as the basis to represent spatial features. Second, we heuristically determine a suitable quantization step-size for visual features to better tolerate spatial variations of similar video clips and propose a paired quantizer method. Third, we incorporate the compactness and/or continuity of matched common sub-sequences in the LCS measure to better reflect temporal characteristics of video. The performance of the proposed algorithm shows an improvement of 63.5% in terms of MAP (mean average precision) as compared to an existing algorithm. The results show that our approach is effective for news video retrieval.