Wolfgang Müller and Andreas Henrich,
Faster Exact Histogram Intersection on Large Data
Collections Using Inverted VA-Files,
In Proceedings of the Third International Conference on Image
and Video Retrieval (CIVR 2004),
Dublin, Ireland, No. 3115 in Lecture Notes in Computer Science, pp. 455-463, Springer-Verlag, July 21-23 2004.Most indexing structures for high-dimensional vectors used in multimedia retrieval today rely on determining the importance of each vector component at indexing time in order to create the index. However for Histogram Intersection and other important distance measures this is not possible because the importance of vector components depends on the query. We present an indexing structure inspired by VA-file and Inverted file that does not need to determine the importance at indexing time in order to perform well. Instead, our structure adapts to the importance of vector components at query processing time. Success of this approach is demonstrated in experiments on feature data extracted from a large image collection.