Say we have $x_i, \ldots, x_n \in R ^ D$ with positive, real components and use Jaccard distance
$$d(x_i, x_j) = 1 - \frac{\sum_{d = 1}^D\min(x_i^d, x_j^d)}{\sum_{d = 1}^D\max(x_i^d, x_j^d)}$$
to find $k$ nearest neighbors for every point. I wonder, is it possible to get exact solution (all $k$ neighbors are found) without computing all pairwise distances?
