编者的总结

本文的核心贡献在于，将度量空间的算法代码中常用的距离计算和比较，通过定界改写。定界的主要根据是三角不等式，基于的信息是数据集上已经计算过的距离表示，具体的方法，就是将与两个对象都直接相邻（已知距离）的对象遍历，套用三角不等式。

1 INTRODUCTION

大量的基于距离的算法，几乎都有以下的编程模式：

image.png

重复的距离计算，比较，然后决策做事。

所谓的直接适合测试，实际上就是检测距离判断为真或假，文中通过构建不等式方程组，看方程组是否有解来判断。
如图所示，对于一组对象，我们知道其中一些的距离，不知道其他的距离，基于这些条件，生成下面一些不等式：

对于已知距离的边，可以生成两个不等式：
- $x_{01} -0.2 \leq 0, -x_{01} + 0.2 \leq 0$
对于未知距离的边，我们可以根据距离的值域（假设为【0,1】），设置0-2个不等式：
- $x_{12} \leq 1, -x_{12} \leq 0$
- 上面这两条使得每两个点必能产生两个不等式，共有2 * C(2,n)个不等式。
由于（弱）三角不等式成立，每3个点，可以生成3个三角不等式
- $x_{12} -x_{23}-x_{13} \leq 0, -x_{12}-x_{23}+x_{13} \leq 0, -x_{12} + x_{23}-x_{13} \leq 0$
- 这会产生3 * C（3，n）条不等式。
对于IF判断式中的两个距离，比如 $x_{26} - x_{35} < 0$ ，我们将其取反， $-x_{26}+x_{35}\leq 0$ ，加入不等式组。
这样最终生成了一个不等式方程组
- A是系数矩阵，X是未知距离的向量，b是已知系数。
- 只要不等式系统无解，也就是没有合适的区域可以进行表征解空间，那么刚才的IF语句 $x_{26} - x_{35} < 0$ 可以认为是真，否则就要去计算真实距离了。
  image.png

然而由于解线性不等式方程组目前最好的复杂度也要 $O(n^6)$ ，所以完全解出来不可能了。

我们可以将IF语句这样进行改写，使其条件更苛刻：

image.png

下面我们对界限进行估计：

我们将所有数据点作为图G中的点，G是一个完全图，图中的边权是两点之间的距离。有的权重是知道的，有的是不知道的。

定义：TUB(Tightest upper bound)，考虑所有已知的距离，在不违背三角不等式的情况下，两点之间最大的可能距离。
- 很容易想到，TUB就是两点之间的最短路（只考虑已知边），根据是（弱）三角不等式中，两边之和大于等于第三边。
定义：TLB（Tightest lower bound），定义和TUB同理。
- TLB利用的是下图的原理：假设我们要估量x和y之间的距离，对于任意一条已知的边(i,j)，我们首先找到x到i的最短路，y到j的最短路，那么x和y的距离，至少是(i,j)的距离减去两个最短路，极端情况如下图的下部分所示。
- 我们利用所有的已知边做一次测量，得到最大的LB，就是TLB。
  
  image.png