Exact constant found for dimension in Jaccard distance space
The exact asymptotic constant in the metric dimension of Jaccard space
Discrete Mathematics
Summary
The paper solves a math puzzle about how to best describe the distance between sets using something called the Jaccard distance, which measures how different two groups are. Previous work only knew the general size of the answer, but these authors figured out the exact number that explains how complex this description can be as the size of the original set grows. They did this by connecting the problem to another known puzzle involving weighing coins to detect differences. Their work sharpens previous estimates into a precise formula.
What this means in practice
- •For data scientists: Design smaller sets of representative features for comparing large collections of sets using Jaccard distance more efficiently.
- •For network engineers: Optimize sparse data representations or sketches used in network similarity detection by better understanding the limits of Jaccard-based metrics.
A theory result. No direct application yet.
Authors
Bjørn Kjos-Hanssen
Abstract
Let $X$ be a finite set with $|X|=n$ and let $\mathrm{Jac}(a,b)=|a\,\triangle\, b|/|a\cup b|$ be the Jaccard distance on the power set $2^X$. Lladser and Paradise recently proved that the metric dimension of $(2^X,\mathrm{Jac})$ is $Θ(n/\ln n)$, with the constant left open; their bounds are $(\ln 2)\,n/\ln n\lesssim β(2^X,\mathrm{Jac})\lesssim 2\ln(2e)\,n/\ln n$. We determine the constant: \[ β(2^X,\mathrm{Jac})=\frac{2n}{\log_2 n}\,(1+o(1))=(2\ln 2)\,\frac{n}{\ln n}\,(1+o(1)). \] The proof identifies the problem, on each ``slice'' of subsets of fixed cardinality, with the Erdős--Rényi coin-weighing problem for a spring scale (the problem of \emph{detecting matrices}). The lower bound is the Erdős--Rényi entropy argument applied to the middle slice; the upper bound follows from the explicit detecting families of Lindström and of Cantor and Mills, augmented by a single extra landmark that reveals cardinality.