Algorithms for Metric Space Embeddings

CCR-9820879

Farach-Colton

Manipulating metric spaces is a basic task in many areas. Clustering, data visualization, and nearest neighbor searches are some of the standard primitives which come up in almost any data-intensive domain. One of the most useful unifying approaches to addessing these problems involves the notion of an embedding. In an embedding, an input metric is mapped into another metric for which useful algorithms have been developed.

This project considers basic algorithmic problems in metric space embeddings. Some of the problems were abstracted from work in image database indexing, protein database indexing and phylogency construction. However, most problems studied are basic algorithmic questions.