Large databases of patterns have emerged as an important tool for
storing information in a wide variety of domains. Such large databases can
capture the wide variability of the data that we observe in the real world, and
allow us to reliably recognize new patterns by comparing them to their
nearest neighbors in the database. At the same time, retrieving nearest
neighbors can often be too slow to be practical, especially in domains
that use computationally expensive similarity measures. Examples of such
measures include dynamic time warping for time series, shape context matching for
edge images, or the edit distance for strings and biological sequences.

BoostMap is an embedding algorithm that can significantly speed up
retrieval in such spaces. Patterns are embedded into a real vector space, where
distances can be measured rapidly using the Manhattan metric. The
mapping is explicitly optimized to preserve a large amount of nearest neighbor
information from the original space. The key novelty of BoostMap is that
it formulates embedding construction as a machine learning task. This
formulation allows the use of powerful machine learning methods (namely
AdaBoost) for embedding optimization. In experiments with different
datasets, including time series and images of handwritten digits,
BoostMap significantly speeds up nearest neighbor retrieval and classification,
and compares favorably to existing embedding methods.