In this paper we propose an efficient and robust method to automatically discover unknown short video repeats with arbitrary lengths, from a few seconds to a few minutes, from large video databases or streams. The proposed method consists of non-uniform video segmentation, self-similarity analysis, locality sensitive hashing, and video repeat boundary refinement. In order to achieve efficient and accurate processing feature extraction and similarity measure are performed at two levels: video frame level and video segment level. Experiments are conducted on 12 hour CNN/ABC news, and 12 hour documentaries (Discovery and National Geography), high recall and precision of 98% - 99% have been achieved. Video repeats' boundaries can be located within several frames. Applying the proposed method for video structure analysis is also briefly discussed