The ability to assess similarity between two objects, and to find in a database examples similar to a given instance, is central to many statistical learning methods. In many cases, using an "off-the-shelf" distance in the input space to measure similarity does not capture the concept of similarity relevant to the task at hand. Instead, much attention has recently been paid to the idea of learning similarity or distance from user-provided examples of what is deemed similar (and, optionally, dissimilar). In this talk, I will describe methods that rely on greedy construction algorithms, and are aimed at learning an embedding of data into a metric space where the underlying similarity is explicit, and thus easy to evaluate. I will also discuss application of these methods to problems in computer vision, where the use of learned similarity proves helpful.