对于欧几里得距离，通常使用kd 树之类的数据结构来解决最近邻和范围搜索问题。使用普通的二叉搜索树，您知道根左侧的所有节点的键都小于根的键，同样，右侧的所有节点的键都大于根的键。kd 树使用类似的想法，只是在每个级别上交替维度。wiki 文章有更深入的解释和一些示例。

如果您的数据点多于 ，则可以有效地完成最近邻搜索（例如 ） 。高维数据很难。$O(k \log n)$$2^D$

kd 树的一个很好的实现可以在scipy中找到；有一个用 C 编写的版本非常有效。您可以在 scipy 中您可能必须相应地调整他们的代码。还有一些替代方案，例如M-tree，它们专门针对度量空间中的数据；有人似乎有一个实现，但我还没有尝试过。$p$

其他类似的数据结构是四叉树和R-trees。我发现四叉树是易于实现与效率的最佳比率，但您的里程可能会有所不同。

C++ 库 mlpack ( http://www.mlpack.org ) 目前包含少数树类型的实现；最令人感兴趣的可能是覆盖树（参见“最近邻居的覆盖树”，Beygelzimer、Kakade 和 Langford，ICML 2006）。覆盖树将适用于满足三角不等式的任何度量。这不适用于树、八叉树（和变体）或 M 树。$kd$

因为 Jaccard 距离确实满足三角不等式，所以您可以轻松编写一个带有 Evaluate() 函数的 JaccardDistance 类，用于计算两点之间的 Jaccard 距离。然后，您可以使用 Jaccard 距离在这些点上构建覆盖树，并轻松运行精确的个最近邻。$k$

请参阅本教程：http ://www.mlpack.org/doxygen.php?doc=nstutorial.html

那么，给定一些 JaccardDistance 类，您可以编写看起来有点像这样的代码......

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);

我没有测试过那个或任何东西；那只是一个草图。但这应该足以让您开始使用 Jaccard 距离进行最近邻搜索的快速算法。

也可以调整 mlpack -tree 实现以使用 Jaccard 距离，但这不会那么简单，这就是为什么为了简单起见我推荐覆盖树的原因。$kd$