New retrieval applications support flexible comparison for all-pairs best match operations based on a notion of similarity or distance. The distance between items is determined by some arbitrary distance function. Users that pose queries may change their definition of the distance metric as they progress. The distance metric change may be explicit or implicit in an application (e.g., using relevance feedback). Recomputing from scratch the results with the new distance metric is wasteful. In this paper, we present an efficient approach to recomputing the all-pairs best match (join) operation using the new distance by re-using the work already carried out for the old distance metric. Our approach reduces significantly the work required to compute the new result, as compared to a naive re-evaluation.