BurkhardKeller Tree（BKTURE）的C++实现
cppbktree的Python项目详细描述
安装
只需从PyPI安装即可：
pip install cppbktree
使用
^{pr2}$由于Python／C++接口，目前该BK树仅限于BytReamming的汉明距离。 欢迎拉取请求。在
基准
基准测试包括在树中插入不同数量的随机64位元素，然后以不同的距离查询值。 这样做了五次，以得到用误差条绘制的标准偏差的提示。在
比较pybktree与cppbktree
在这个log-log图中，可以看到查找和创建遵循各种次线性幂律。
在深度为$d$的树中插入一个元素大约需要O(log(d))汉明距离计算。
假设一个均匀分布的树，元素的数量被指定为N=d^n，其中n是度量返回的最大距离。
对于hamming距离，n是散列的位数。
求解这个深度，得到d=log N / log n。
如果您只对N的依赖性感兴趣，那么log n可以看作是一个小的常量因子。
从此以后，树的创建应该遵循O(\sum_i^N \log i) = O( log( \product_i^N i ) ) = O(log(N!))。
用斯特林近似法得到O(log(sqrt(N) N^N)) = O(log(N^(N+1/2))) = O(N log(N))。
但是，log(N)是一个增长非常缓慢的函数，因此树的创建看起来几乎是一个线性函数。在
pybktree和cppbktree都在大约1e4个元素处有一些跳跃，但只有cppbktree作为~2e6个元素的第二个跳转，但仅当查找距离为<；=16的元素时。 我无法解释这些跳跃。 它们看起来就像内存缓存效果。 由于这些跳跃，10米元素的有效加速因查找距离而异。 只有树的创建缩放是一条非常平滑的曲线，除了一些运行时较小的异常值。在
以下是拟合曲线的幂律：
| operation | pybktree | cppbktree |
|---|---|---|
| Tree creation | 1.12e-06 N^1.12 | 4.92e-07 N^1.05 |
| Distance threshold 0 | 2.04e-06 N^0.27 | 4.19e-07 N^0.27 |
| Distance threshold 1 | 2.06e-06 N^0.37 | 2.77e-07 N^0.38 |
| Distance threshold 2 | 1.68e-06 N^0.51 | 1.76e-07 N^0.54 |
| Distance threshold 4 | 1.36e-06 N^0.73 | 1.11e-07 N^0.74 |
| Distance threshold 8 | 1.10e-06 N^0.92 | 7.47e-08 N^0.94 |
| Distance threshold 16 | 1.05e-06 N^0.99 | 4.93e-08 N^1.05 |
在这里，对于一棵树和一棵树，有10万个加速和运算元素：
^{tb2}$cppbktree在pybktree上的加速比在~2和10之间变化。 对于较小的树，加速效果会更好。 只有树的创建时间加速与树的大小无关，大约为5。在
pybktree与vTree的比较
至少在这个只有64位散列和hamming距离作为度量的基准测试中，至少在VP树的纯python实现中，结果是相当令人失望的。 vptree模块几乎总是比较慢。 查找实际上与pybktree非常相似（这意味着仍然比cppbktree的查找慢），但是树的创建速度慢了整整一个数量级。 对于100k个元素，这导致pybktree比vptree快7.7倍。在
- 项目
标签：
欢迎加入QQ群-->： 979659372
