Skip to main content

The trick is to use a transform called the Steinhaus Transform. Given a metric $(X, d)$ and a fixed point $a \in X$, you can define a new distance $D'$ as $$D'(x,y) = \frac{2D(x,y)}{D(x,a) + D(y,a) + D(x,y)}.$$ It's known that this transformation produces a metric from a metric. Now if you take as the base metric $D$ the symmetric difference between two sets and empty set as $a$, what you end up with is the Jaccard distance (which actually is known by many other names as well).

For more information and references, check out Ken Clarkson's survey Nearest-neighbor searching and metric space dimensions (Section 2.3).

Suresh Venkat
  • 4.5k
  • 1
  • 26
  • 33