Modeling moving objects and handling various types of motion queries have become an interesting topic to investigate in the area of video databases. In one type of motion queries, motion of multiple objects is specified by the changes in relative spatial positions of objects. Answering such kind of queries, that involve motion of multiple objects whose identifications are not specified, requires some type of indexing because the time complexity of processing such a query in the absence of an index structure is O(N!/(N-n)!), where N is the number of objects in the database and n is the number of objects in the query. In th$ SMIST-index, and compare its performance against a similar scheme. That scheme consists of a constraint satisfaction algorithm, which is called Join Window Reduction (JWR), combined with a spatial index structure (R*-tree). Experimental results indicate that SMIST-index outperforms the JWR algorithm. Also, SMIST-index is shown to be scalable to increasing number of frames and objects.

Key words: Motion, video, database, multimedia, spatial, temporal, indexing.