Image retrieval results are sensitive to the particular distance metric used. It would be interesting to know if the authors have any intuition why L1 norm works better than L2 norm.

It's also interesting that in table 1 the best image retrieval performance for vocabulary size 10K is for a non-hierarchical tree. I guess for performance the hierarchy makes a lot of sense though.