A note on the triangle inequality for the Jaccard distance

TL;DR

The paper addresses proofs of the triangle inequality for Jaccard distances defined through nonnegative, monotone, submodular functions. It gives two direct proofs, establishes related validity results, and identifies scope boundaries for the underlying function class.

• Problem

  The paper studies how to prove the triangle inequality for generalized Jaccard distances based on nonnegative, monotone, submodular functions.

• Method

  It develops two simple, direct proofs connecting Jaccard distance inequalities with modular and submodular set-function properties.

• Results

  The results establish the triangle inequality for standard, generalized, and Steinhaus Jaccard distances, with Jδ,f also a pseudometric for budget-restricted linear costs and bipartite-graph neighborhood size.

• Takeaways & Limitations

  Theorem 4 motivates J∆δ,f as the appropriate submodular Jaccard distance and its inverse as the corresponding similarity index.

• Takeaways & Limitations

  Theorem 3 is not generally valid for all nonnegative, monotone, submodular functions; budget-restricted linear costs and bipartite-graph neighborhood size provide counterexample settings.