On the Triangle Inequality for the Jaccard Distance in Arbitrary Lattices
The math behind Jaccard distance, the classic similarity score, now proven to work as a true distance on much broader mathematical structures than sets
Jaccard similarity is a century-old way to score how much two sets overlap, and turning it into a distance requires it to satisfy the triangle inequality to count as a real metric. Older proofs of this leaned heavily on set-specific or Boolean-algebra-specific properties like distributivity and having a universal top and bottom element, which don't exist in more general structures called lattices. This paper pins down exactly which properties of the valuation function (the function measuring the 'size' of an element) are needed for the triangle inequality to hold across arbitrary lattices, relatively complemented distributive lattices, and sectionally complemented distributive lattices, plus proves what must fail if it doesn't hold.
METAL MEDIA explanatory visual
The math behind Jaccard distance, the classic similarity score, now proven to work as a true distance on much broader mathematical structures than sets
- 01Classic proofs that Jaccard distance satisfies the triangle inequality (the rule that a direct path is never longer than one through a middle point) depended on Boolean algebra features like distributivity and global top/bottom elements, which don't carry over to general lattices.
- 02The authors show that if the valuation function is strictly positive, monotone, and modular (sum of values on the union and intersection equals sum of values on the two elements), the triangle inequality holds on any lattice at all, with no distributivity needed.
- 03For supermodular (synergy-like) and log-submodular valuations, the triangle inequality holds on relatively complemented distributive lattices, meaning no global maximum or minimum element is required, only local structure within any bounded interval.
- 04For submodular valuations, they adapt a symmetric-difference version of the Jaccard formula and prove it works on sectionally complemented distributive lattices, and they also show supermodularity is a hard necessary condition, meaning the standard formula simply cannot be a valid metric without it.
- 05These results extend the reach of Jaccard-style distance to structures like the non-distributive lattices of quantum information theory, formal concept analysis, and open-ended data streams that previous theory couldn't cleanly cover.
What they did
- Classic proofs that Jaccard distance satisfies the triangle inequality (the rule that a direct path is never longer than one through a middle point) depended on Boolean algebra features like distributivity and global top/bottom elements, which don't carry over to general lattices.
- The authors show that if the valuation function is strictly positive, monotone, and modular (sum of values on the union and intersection equals sum of values on the two elements), the triangle inequality holds on any lattice at all, with no distributivity needed.
- For supermodular (synergy-like) and log-submodular valuations, the triangle inequality holds on relatively complemented distributive lattices, meaning no global maximum or minimum element is required, only local structure within any bounded interval.
- For submodular valuations, they adapt a symmetric-difference version of the Jaccard formula and prove it works on sectionally complemented distributive lattices, and they also show supermodularity is a hard necessary condition, meaning the standard formula simply cannot be a valid metric without it.
- These results extend the reach of Jaccard-style distance to structures like the non-distributive lattices of quantum information theory, formal concept analysis, and open-ended data streams that previous theory couldn't cleanly cover.
| (X∨Y)∧Z | =(X∧Z)∨(Y∧Z)∀X,Y,Z∈L | (11) | ||
|---|---|---|---|---|
| (X∧Y)∨Z | =(X∨Z)∧(Y∨Z)∀X,Y,Z∈L |
Why it matters
Jaccard distance underpins practical tools like nearest-neighbor search pruning, speeding up k-means clustering, and approximation guarantees for routing problems, all of which rely on the triangle inequality actually holding. This work tells practitioners exactly when Jaccard-style distances remain mathematically valid outside plain sets, including in quantum logic, concept hierarchies, and streaming data settings.
Terms in this paper
- Jaccard similarity · a 0-to-1 score measuring how much two sets overlap relative to their combined size
- triangle inequality · the requirement that a direct distance between two points never exceeds the distance through a third point
- lattice · an ordered structure where every pair of elements has both a well-defined 'join' (least upper bound) and 'meet' (greatest lower bound)
- modular / supermodular / submodular valuation · a function whose value on the join and meet of two elements sums to exactly, more than, or less than the sum of their individual values
- relatively/sectionally complemented distributive lattice · a lattice obeying distributivity where, within any bounded interval, elements have a counterpart that combines with them to hit the interval's min and max
Original abstract (English)
This paper presents new theoretical results on generalizing the Jaccard distance for lattices and real valuations. We demonstrate that when the valuation is strictly positive, monotone, and modular, the Jaccard distance satisfies the triangle inequality on arbitrary lattices, effectively generalizing earlier results that depended heavily on distributivity. Moving to relatively complemented distributive lattices (which safely drop the requirement for the global bounds found in Boolean algebras), we prove the triangle inequality holds as long as the valuation is positive, monotone, supermodular, and $\log$-submodular. Additionally, we adapt the symmetric-difference Jaccard formulation for submodular valuations to sectionally complemented distributive lattices. Shifting to necessary conditions, we prove that supermodularity is a strict requirement for the standard generalized Jaccard distance to operate as a valid metric. Finally, we map the practical value of relaxing these structural constraints to computational fields like quantum information theory, formal concept analysis, and machine learning, closing with a brief look at open mathematical problems.
Read on arXivLatest papers
- SWE-bench Science: Can Coding Agents Resolve Engineering Tasks in Science?AI coding agents were tested on fixing real scientific software, and even the best one failed more than half the time
- FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM ServingMaking sparse attention fast enough and accurate enough for real LLM serving, not just papers
- PolicyGuide: From Guarding One Action to Guiding the Whole Workflow for Policy-Compliant LLM AgentsMaking customer-service AI agents follow the whole procedure, not just avoid one bad action
- EXIMO: VLM Guided Exploration of VLA PoliciesTeaching a robot new chores without human teleoperation, by letting a chatty AI supervise it
- EnvHarness: Awakening Static Worlds for Agent LearningInstead of building new training worlds from scratch, this work adds a plug-in layer that reshapes existing ones around each agent's actual weaknesses
- Bounded Sovereignty and the Control Tax: Pricing AI Oversight When the Deployer Does Not Own the ModelCompanies that rent AI instead of owning it can only do half of AI safety oversight
- Beyond Imitation: Filtering On-Policy Distillation by Reasoning ProgressA fix for AI models that get penalized by their teacher even when they're reasoning correctly
- PersonalBench: Measuring the Authorship Gap in LLM PersonalizationAI can be prompted to write 'like someone,' but its own voice never fully disappears