A method of testing a video against an aggregate query includes automatically receiving an aggregate query defining participant(s) and condition(s) on the participant(s). Candidate object(s) are detected in the frames of the video. A first lattice is constructed for each participant, the first-lattice nodes corresponding to the candidate object(s). A second lattice is constructed for each condition. An aggregate lattice is constructed using the respective first lattice(s) and the respective second lattice(s). Each aggregate-lattice node includes a scoring factor combining a first-lattice node factor and a second-lattice node factor. respective aggregate score(s) are determined of one or more path(s) through the aggregate lattice, each path including a respective plurality of the nodes in the aggregate lattice, to determine whether the video corresponds to the aggregate query. A method of providing a description of a video is also described and includes generating a candidate description with participant(s) and condition(s) selected from a linguistic model; constructing component lattices for the participant(s) or condition(s), producing an aggregate lattice having nodes combining component-lattice factors, and determining a score for the video with respect to the candidate description by determining an aggregate score for a path through the aggregate lattice. If the aggregate score does not satisfy a termination condition, participant(s) or condition(s) from the linguistic model are added to the condition, and the process is repeated. A method of testing a video against an aggregate query by mathematically optimizing a unified cost function is also described.