Metric-based shape retrieval in large databases

This paper examines the problem of database organization and retrieval based on computing metric pairwise distances. A low-dimensional Euclidean approximation of a high-dimensional metric space is not efficient, while search in a high-dimensional Euclidean space suffers from the curse of dimensionality. Thus, techniques designed for searching metric spaces must be used. We evaluate several such existing exact metric-based indexing techniques, and show that they require extensive computational effort. This motivates the development of an approximate nearest neighbor search technique where the k nearest neighbors are used to approximate the local neighborhood of a point. The resulting kNN graph is searched in a best-first fashion producing excellent indexing efficiency.