The spatio-temporal information of a video object is important for content-based video retrieval. In this paper, the spatio-temporal information of a video object, such as the velocity, location and orientation of a video object, is represented by an ST-string. Since the user may not be interested in all spatio-temporal information, the user query can be represented by a QST-string which contains some spatio-temporal information only, such as the velocity and orientation of a video object. Therefore, the video retrieval problem can be transformed into the problem of approximately matching a QST-string with ST-strings. A general solution is proposed in this paper, which includes a similarity measure, an index structure and the corresponding matching methodology. The experiment results show that both the approximate and exact results can be found efficiently via the proposed index structure and the matching algorithm.