In an earlier paper, we designed a similarity based video retrieval system. Queries are specified in a language called Hierarchical Temporal Language (HTL). In this paper, we present several extensions of the HTL language. These extensions include queries that can have the negation operator and any other logical and temporal operators such as disjunction. Efficient algorithms for processing queries in the extended language are also presented.