Efficient indexing is a key in content-based video retrieval solutions. In this paper we represent video sequences as traces via scaling and linear transformation of the frame luminance field. Then an appropriate lower dimensional subspace is identified for video trace indexing. We also develop a trace geometry matching algorithm for retrieval based on average projection distance with a locally embedded distance metric. Simulation results demonstrated the high accuracy and very fast retrieval speed for the proposed solution.