标题：一个通用的方法用来减少昂贵的距离计算，可用于广泛的距离问题

编者的总结

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

1 INTRODUCTION

1.1 Novelty, Motivation, and Applications

1. 本文讨论的范围在度量空间，满足三角不等式，或者放松的三角不等式。
2. 本文讨论的问题中，距离计算是算法瓶颈。
3. 本文提出的是一个统一的优化框架，不改变原算法结果，只减少距离计算次数，同时增加少量CPU计算开销。

2 DISTANCE COST MINIMIZATION

2.1 Working Principles of Proximity Algorithms

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

image.png

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

2.2 Direct Feasibility Test

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

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

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

3 GRAPH THEORETIC APPROACH

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

image.png

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

3.1 Data Model

我们将所有数据点作为图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

3.2 Problem Definitions

• 问题1：如何在不调用距离函数的情况下，考虑所有已知距离和三角不等式，为节点间距离定界。
• 问题2：在不得已调用了距离函数的情况下，如何更新图结构，跟踪仍然是未知边的界限。

4 BOUND COMPUTATION ALGORITHMS

4.1 Exact Algorithms

精确定界的思想，我们在上面已经介绍过了，下面介绍具体流程。
要想算的界，前提条件是：

1. 算和到所有其它节点的最短路，算法使用Dijkstra算法；
2. 和之间的最短路，就是TUB；

3. 对于所有已知边，做一次极端相减不等式原理（上面讲到的），在找到的下界中，保存最大的。

   
   image.png

• 性能分析：m为已知边数量，n为节点数量

  • Dijkstra算法代价为，做两次单源最短路；
  • 每条边进行遍历：复杂度O(m)
  • 总的复杂度为

• 更新算法：只需要更新图结构即可，代价O（1）

4.2 Approximate Algorithms

近似算法称为Triangle Induced Solution Scheme（Tri Schema）三角形诱导的解决方案模式。
具体的算法，就是根据节点id，不断找i,j共同的邻居节点，然后利用三角不等式更新上下界。

image.png

• 近似算法的期望运行时间是O(m/n)