Sergey Brin
目录
背景
大度量空间：一个度量空间，球的体积随着半径的增大增长得非常快。
GNAT目的是解决大度量空间中的近邻查询问题。
基因序列比对、声音识别、图片识别等数据都在分布上存在一定关联性，利用这些关联性可以提升近邻搜索的性能。为了达到这个目的，要求数据结构能够反映数据的内在几何特征。GNAT通过在多个层次上将数据分割为多个区域来保留基本几何结构。
对比VPT，由于球外的空间总是比球内的大，在大度量空间中，球外的数据分布会变得非常稀疏，从而降低索引性能。
算法
构建
- 从需要建立索引的数据集选择k个划分点p1,…,pk，（也是一般所说的度），这些点是随机选取的，但我们保证它们之间相距比较远（fairly far apart）。
- 我们将剩余的点根据与它最近的划分点关联(associate)起来，将与划分点Pi关联的点集记为Dpi
- 对于每一对划分点
(pi, pj)，计算range(pi, Dpj)=[mind_d(pi, Dpj), max_d(pi, Dpj)]，即点pi到点集Dpj距离的最大值和最小值。 - 递归地对每一个Dpj建树，可能使用不同的度。
查询
- 假设我们需要查找距离点x小于r的所有点，P表示当前结点的所有划分点（最开始是GNAT的头部结点）。最开始P包括当前结点的所有划分点。
- 从P中选取一个点p（这个点不会重复），计算距离
Dist(x, p)，如果Dist(x, p)<=r，将点p加入结果集中。 - 对于P中的所有点q，如果
[Dist(x, p)-r, Dist(x, p)+r] ∩ range(p, Dq)为空集，那么就将q从P中移除。可以通过以下方法证明：假设y是Dq中的任意点，如果Dist(y, p) < Dist(x, p)-r，那么根据三角不等式，我们可以得到Dist(x, y)+Dist(y, p) >= Dist(x, p)，因此Dist(x, y) > r. 另外，如果Dist(y, p) > Dist(x, p)+r，我们可以由三角不等式Dist(y, x)+Dist(x, p) >= Dist(y, p)得到Dist(x, y) > r。 因此点y不可能落在范围[Dist(x, p)-r, Dist(x, p)+r]，不然会与range(p, Dq)出现交集。 - 对P中的剩余所有点重复步骤2和3
- 对于P中所有剩余的点pi，递归搜索Dp
选择划分点
选点的时候我们希望划分点尽量地随机，这样就会使这些划分点更接近聚簇的中心点。如果选择的划分点比较接近，我们计算它们之间距离的时候得到的信息就会更少，因为不同两个分支之间计算得到的距离非常接近。在这，如果多个划分点处于同一个聚簇中，会将这个聚簇过度划分。
首先随机选取一个候选点，然后选择离它最远的点作为第二个候选点，再选出离这两个点最远的第三个点（第三个点离前两个点距离的较小值是最大的）。以此类推，知道选出足够多的候选点作为划分点。这个过程可以通过动态规划算法进行，时间复杂度为O(mn)。其中n是候选点，m是最后划分点的数量。
上述划分点选取过程将进行三次，选出的点成为候选点。然后选取最分散的候选点集。
选择结点的度以及使树平衡
通过赋予数据点较多的子树更多的度，来平衡子树。赋给根节点一个度k，它的每个孩子结点根据包含的数据点，成比例地被分配一个度，使得孩子的平均度等于全局度k. 递归地进行这个过程，使每个孩子的平均度都为k（忽略最高度和最低度）。
参考资料
[1] Near Neighbor Search in Large Metric Spaces
