The trajectory of moving objects in video data plays an important role in video indexing for content-based retrieval. In this paper, we propose a new spatio-temporal representation scheme for modeling moving objects’ trajectories in video data. In order to support contentbased retrieval on video data very well, our representation scheme considers the moving distance of an object during a given time interval as well as its temporal and spatial relations. Based on our representation scheme, we present two similarity measures for both the trajectory of a single moving object and those of multiple moving objects, which provide ranking for the retrieved video results. Finally, we show from our experiment that our representation scheme achieves about 10-20% higher precision while it holds about the same recall, compared with its competitors, such as Li’s and Shan’s schemes.