Efficient Shape Indexing Using an Information Theoretic Representation

Efficient retrieval often requires an indexing structure on the database in question. We present an indexing scheme for cases when the dissimilarity measure is the Kullback-Liebler (KL) divergence. Devising such a scheme is difficult because the KL-divergence is not a metric, failing to satisfy the triangle inequality or even .niteness in general. We de.ne an optimal represenative of a set of distributions to serve as the basis of such an indexing structure. This representative, dubbed the exponential information theoretic center, minimizes the worst case KLdivergence from it to the elements of its set. This, along with a lower bound on the KL-divergence from the query to the elements of a set, allows us to prune the search, increasing e.ciency while guarenteeing that we never discard the nearest neighbors. We present results of querying the Princeton Shape Database which show significant speed-ups over an exhaustive search and over an analogous approach using a more mundane representative.