I was impressed by the paper's continual focus on implementation issues, whether it be the tree structure for efficiency, the ability to "on-the-fly" add new images to the database or even the use of real video data (not all lab photos!) in their results.
I am not really sure what the entropy is talking about in the paper. But it got me thinking (uh-oh). In information theory, when you are trying to maximize the compression of a symbol alphabet, you are trying to minimize the entropy. As the symbols become less likely to occur the number of bits assigned to describe the symbol increases. Doing this ideally (say Huffman Encoder) will then minimize the entropy of the alphabet and maximize the compression. My idea, is why not be keeping track of the probabilities of object matches for each of the nodes in the search tree and have variable length branches. The most frequently found objects would then have very short branches and the least frequently found objects would have much longer search branches. This would reduce the average search for each object in the tree.
The paper may have addressed this issue with the "stop lists" but I didn't quite follow it.