A note on the triangle inequality for the Jaccard distance

Abstract Two simple proofs of the triangle inequality for the Jaccard distance in terms of nonnegative, monotone, submodular functions are given and discussed.

cs.DM cs.IR cs.LG stat.ML Mathematics Computer Science

Source

Paper

References (21)

01Submodular Hamming MetricsJennifer Gillenwater, Rishabh K. Iyer, Bethany Lusch et al.2015 · Neural Information Processing Systems · 14 citations In Library

02Encyclopedia of DistancesM. Deza, E. Deza2014 · 1.9k citations

03Similarity, Dissimilarity, and Distance, Measures ofJ. Gower, M. Warrens2014 · 33 citations

04Measuring Distance between Unordered Sets of Different SizesAndrew Gardner, Jinko Kanno, C. A. Duncan et al.2014 · 2014 IEEE Conference on Computer Vision and Pattern Recognition · 54 citations

05Metrics based on average distance between setsO. Fujita2011 · Japan journal of industrial and applied mathematics · 38 citations

06Metrics for Mining MultisetsW. Kosters, J. Laros2007 · SGAI Conferences · 27 citations

07Encyclopedia of Statistical SciencesJoseph E. Cavanaugh2007 · 517 citations

08Similarity, Dissimilarity, and Distance MeasureJ. Gower2005 · 12 citations

09Similarity estimation techniques from rounding algorithmsM. Charikar2002 · Symposium on the Theory of Computing · 2.8k citations

10A proof of the triangle inequality for the Tanimoto distanceA. H. Lipkus1999 · 239 citations

11Combinatorial optimizationW. Cook, W. Cunningham, W. Pulleyblank et al.1997 · 2.2k citations

12Minimizing a Submodular Function on a LatticeD. M. Topkis1978 · Operational Research · 1.5k citations

Scroll for more · 9 remaining

Similar papers

Using Partial Monotonicity in Submodular MaximizationLoay Mualem, Moran Feldman2022 · Neural Information Processing Systems · 13 citations In Library

Tractable Triangles and Cross-Free Convexity in Discrete OptimisationMartin C. Cooper, Stanislav Živný2012 · Journal of Artificial Intelligence Research · 29 citations In Library

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular FunctionsYixing Chen, Alan Kuhnle2026 · 0 citations In Library

New Similarity Correlation Functions for Sets and Binary Data Based on Jaccard Similarity MeasureIldar Batyrshin, Imre J. Rudas2024 · International Symposium on Applied Computational Intelligence and Informatics · 2 citations In Library

Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular MaximizationRad Niazadeh, Tim Roughgarden, Joshua R. Wang2018 · Neural Information Processing Systems · 59 citations In Library

Recognition of k-Distance Monotone Boolean FunctionsHasmik Sahakyan, L.Kh. Aslanyan2025 · Pattern Recognition and Image Analysis In Library

Fast Maximization of Non-Submodular, Monotonic Functions on the Integer LatticeAlan Kuhnle, J. D. Smith, Victoria G. Crawford et al.2018 · International Conference on Machine Learning · 44 citations In Library

New Lower Bounds for Testing Monotonicity and Log Concavity of DistributionsYuqian Cheng, Daniel M. Kane, Zhicheng Zheng2023 · arXiv (Cornell University) In Library

Submodular Hamming MetricsJennifer Gillenwater, Rishabh K. Iyer, Bethany Lusch et al.2015 · Neural Information Processing Systems · 14 citations In Library

Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and ApplicationsChristopher Harshaw, Moran Feldman, Justin Ward et al.2019 · International Conference on Machine Learning · 122 citations In Library

Patents near this paper

Patent US 5,915,247US 5,915,247 DETECTING AND TRACKING MONOTONICITY FOR ACCELERATING RANGE AND INEQUALITY QUERIESUS 7,519,583 · INTERNATIONAL BUSINESS MACHINES CORPORATION · 2009 TWO-DIMENSIONAL AFFINE-INVARIANT HASHING DEFINED OVER ANY TWO-DIMENSIONAL CONVEX DOMAIN AND PRODUCING UNIFORMLY-DISTRIBUTED HASH KEYSUS 5,802,525 · IBM CORPORATION · 1998 APPARATUS FOR SECURE COMPUTATION OF STRING COMPARATORSUS 8,271,796 · TELECOMMUNICATIONS RESEARCH LABORATORY · 2012 THREE-DIMENSIONAL AFFINE-INVARIANT HASHING DEFINED OVER ANY THREE-DIMENSIONAL CONVEX DOMAIN AND PRODUCING UNIFORMLY-DISTRIBUTED HASH KEYSUS 5,799,312 · IBM CORPORATION · 1998

Source of record

arXiv