Isn't this just k-NN? I mean: one can reduce this problem to k-NN by first loading the database with all video frames, and then performing queries using frame 0, frame 1, etc.

There are good tree algorithms[0] and implementations[1][2] for executing k-NN queries. These implementations also exploit the properties of the triangle inequality.

[0] http://en.wikipedia.org/wiki/Ball_tree

[1] http://mlpack.org/doxygen.php?doc=nstutorial.html

[2] http://scikit-learn.org/stable/modules/neighbors.html#neighb...