Annoy是高维空间求近似最近邻的一个开源库。

Annoy构建一棵二叉树，查询时间为O(logn)。

Annoy通过随机挑选两个点，并使用垂直于这个点的等距离超平面将集合划分为两部分。

如图所示，图中灰色线是连接两个点，超平面是加粗的黑线。按照这个方法在每个子集上迭代进行划分。

依此类推，直到每个集合最多剩余k个点，下图是一个k = 10 的情况。

相应的完整二叉树结构：

一个思想依据是：在原空间中相邻的点，在树结构上也表现出相互靠近的特点，也就是说，如果两个点在空间上相互靠近，那么他们很可能被树结构划分到一起。

如果要在空间中查找临近点，我们可以在这个二叉树中搜索。上图中每个节点用超平面来定义，所以我们可以计算出该节点往哪个方向遍历，搜索时间 log n

Annoy解析