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?
Finding nearest neighbors using Jaccard distance for positive, real-valued vectors
computational geometry;nearest neighbors
For the Euclidean distance, it's typical to use data structures like a k-d tree for nearest-neighbor and range search problems. With an ordinary binary search tree, you know that all nodes to the left of the root have keys less than that of the root, and likewise all nodes to the right have keys greater than the root. A k-d tree uses a similar idea only alternating dimensions at each level. The wiki article has a more in-depth explanation and some examples.Nearest-neighbor searches can be done efficiently (e.g. $O(k \log n)$) provided you have more data points than $2^D$. High-dimensional data is hard.A good implementation of a k-d tree can be found in scipy; there's a version written in C which is pretty efficient. You can do nearest-neighbor queries with arbitrary $p$-norms in scipy, but they have not included the Jaccard distance; you may have to adapt their code accordingly. There are alternatives, like the M-tree, which are specifically geared toward data in a metric space; someone appears to have an implementation but I haven't tried it.Other similar data structures are quadtrees and R-trees. I find quadtrees the best ratio of ease-of-implementation to efficiency, but your mileage may vary.