In the previous chapter, we described mechanisms for indexing multimedia data for quick access. The indexing process, in general, is based on establishing some order between the data objects so that queries can be routed toward the ones that are likely to be matches for the query and prune away those objects that are non-matches. Thus, most indexing techniques are based on some form of data clustering. In fact, hierarchical multidimensional index structures are sometimes referred to as self-clustering techniques.

Naturally, establishing an order on the given set of data objects requires an understanding of the fundamental characteristics and features of the media and the use of data structures appropriate for these features. We have seen that the index structures applicable for different media (e.g., sequences, graphs, trees, and vectors) are based on different principles and operate differently from each other.

In many multimedia databases, however, we may not have prior knowledge about the explicit features of data. This is the case, for example, when we have “black-box programs” that can compare two objects or when the similarity of the pair is simply evaluated subjectively by users. In both cases, we can obtain information about distances and/or similarities between pairs of objects, but there are no explicit features that one can use as a basis for an index structure. As we have seen in Section 4.3, one possible solution in these cases is to map or embed the objects into a multidimensional space (using MDS or FastMap) using the available distance values.