Abstract: To effectively retrieve and locate near-duplicate videos, a novel approach of video retrieval and localization was proposed based on relative Levenshtein Distance similarity (LD). In the algorithm, two major components were included, named local descriptor based video coding and relative Levenshtein Distance similarity-based video retrieval and localization. About the local descriptor based video coding, the video key-frames were extracted firstly from data base; then Root-SIFT feature descriptors were extracted from key-frames and all descriptors were clustered to generate a codebook with the Hierarchical K-Means; lastly, each key-frame was assigned a unique visual word and code. About the relative Levenshtein Distance similarity-based video retrieval and localization, each query video was encoded firstly, and then the near-duplicate videos were filtrated, near-duplicate segments were located, and the retrieved videos were re-ranked with the relative Levenshtein Distance similarity-based algorithm. The experimental results show that the LD algorithm can achieve a 8.55% higher effect on the average F₁ evaluation criterion than the algorithm proposed by Yeh et.al, and the NDCR is reduced to 29%.