Inverted file-based indexing for efficient multimedia information retrieval in metric spaces

Content-based similarity search is an important task in multimedia information retrieval (IR). Here, metric space access methods (MAMs) can be applied. They are purely based on the use of a metric distance. No assumption is made about the representation of the feature objects. On the one hand, approximate MAMs have been proposed relying on the inverted file---the de facto standard index structure for text retrieval. On the other hand, there are many exact hierarchical and multi-step MAMs.

We present IF4MI (Inverted Files for Metric Indexing), the first exact metric access method (MAM) based on the inverted file concept. IF4MI can outperform existing MAMs such as the M-tree and the PM-tree. In addition, the pruning power of current state-of-the-art techniques---namely the Metric Index---can be brought to inverted files without relying on an additional mechanism which maps feature objects to one-dimensional values for storing them in adequate data structures such as a B⁺-tree. IF4MI is conceptually appealing since it can make use of extensive knowledge in the field of inverted file-based indexing. As one example, we show how the efficient processing of textual filter queries---an important task in multimedia IR---is inherently supported.