We propose a scheme for faster and more effective retrieval of temporal, spatial and social multimedia from large collections. We define interactive multimedia queries that allow simultaneous query refinement on multiple search dimensions. User interaction techniques based on line and iconic sketches allow specifying queries based on the above definition. We prototype a multi-user travel media network and implement the proposed user interaction techniques for retrieving locomotion patterns of the users. The proposed queries facilitate easy input and refinement of queries, and efficient retrieval.