I think a less stringent, but still workable assumption is that for very similair objects, their distances will be small. This is much easier to accomplish than agreement across all pairs.