Finding nearest neighbors using Jaccard distance for positive, real-valued vectors

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?

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.

The C++ library mlpack (http://www.mlpack.org) currently contains an implementation of a handful of tree types; of the most interest is probably the cover tree (see "Cover trees for nearest neighbor", Beygelzimer, Kakade, and Langford, ICML 2006). The cover tree will work with any metric that satisfies the triangle inequality. This is not true of the $kd$-tree, the octree (and variants), or the M tree.

Because the Jaccard distance does satisfy the triangle inequality, you can easily write a JaccardDistance class with an Evaluate() function that evaluates the Jaccard distance between two points. Then you can build a cover tree on the points using the Jaccard distance and run exact $k$ nearest neighbors easily.

See this tutorial: http://www.mlpack.org/doxygen.php?doc=nstutorial.html

Given some JaccardDistance class, then, you can write code that looks a bit like this...

using namespace mlpack::neighbor;
using namespace mlpack::tree;

extern arma::mat dataset; // The dataset containing the points.
extern size_t k; // The number of neighbors being searched for.
NeighborSearch<NearestNeighborSort, JaccardDistance, CoverTree<JaccardDistance> > ns(dataset);

arma::Col<size_t> neighbors; // Will store the neighbors of each point.
arma::mat distances; // Will store the distances to those neighbors.

ns.Search(k, neighbors, distances);


I haven't tested that or anything; that's just a sketch. But it should be enough to get you started on a fast algorithm to do nearest neighbor search with the Jaccard distance.

It would be possible to adapt the mlpack $kd$-tree implementation to work with Jaccard distances too, but it would not be as straightforward, which is why I recommend the cover tree for the sake of simplicity.