So I saw this question posed on math.se for $d=3$. Suppose we are given a finite set $X \subset {\mathbb Z}^d$ of $n$ points. The goal is to find a hyper box of integer points $ B = [k_{1,1},k_{1,2}] \times [k_{2,1},k_{2,2}] \times \ldots \times [k_{d,1},k_{d,2}] $ so that the Jaccard distance $d(X,B)$ is minimized. The Jaccard distance is $d(X,B) = 1 - |X \cap B| / |X \cup B|$.

So obviously we can just restrict the range of the box to be defined by coordinates of points in $X$ in the appropriate dimension. So there are "only" $O(n^{2d})$ boxes to check. Furthermore, the Jaccard distance can be computed in constant time if $|X \cap B|$ is known, because $|X|$ is known and $|B|$ is easily calculated.

So, since the original problem was formulated for $d=3$, it occurred to me that the computation of $|X \cap B|$ could be reduced to $O(\log ^{d-1} n)$ time (instead of naïve $O(n)$ time) using a modified layered range tree that returns counts of points that satisfy a given range query.

However, I could not think of any way to avoid testing all possible hyper boxes, especially if $X$ is dense. Thus my speed-up is very minor compared to the overwhelming complexity of checking all boxes. Is there a way to speed up to better than $O(n^{2d} \log^{d-1} n)$ time, and if nothing else, at least in certain cases, like if $X$ is dense or sparse?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.