  Prior work presented the sentence tracker, a method for scoring how well a
sentence describes a video clip or alternatively how well a video clip depicts
a sentence. We present an improved method for optimizing the same cost function
employed by this prior work, reducing the space complexity from exponential in
the sentence length to polynomial, as well as producing a qualitatively
identical result in time polynomial in the sentence length instead of
exponential. Since this new method is plug-compatible with the prior method, it
can be used for the same applications: video retrieval with sentential queries,
generating sentential descriptions of video clips, and focusing the attention
of a tracker with a sentence, while allowing these applications to scale with
significantly larger numbers of object detections, word meanings modeled with
HMMs with significantly larger numbers of states, and significantly longer
sentences, with no appreciable degradation in quality of results.
