Many state-of-the-art video clip identification algorithms are based on ordinal measures. However, they still have two problems: The weak uniqueness of video signature makes the precision decreases quickly as recall increases high enough; Quadratic-time complexity makes the response time too long and sensitive to the length of query video. To address these two problems, this paper proposes a video clip identification algorithm based on spatiao-temproal ordinal measures. The key steps are: (1) Before the accurate identification starts, it employs a linear-time complexity real-time filtration method based on spatio-temporal binary pattern histogram (STBPH) and a fast filtration method based on binary temporal ordinal measure (BTOM) to filter out most candidate video clips in target video; (2) During the accurate identification process, it utilizes joint spatio-temporal ordinal measure (JSTOM) which is more unique and robust in improving the precision. Experimental results show that the approach improves the precision significantly and is very efficient and insensitive to the length of query video.