标题：高维数据近似NN搜索-实验、分析、优化
这是一篇针对广义KNN算法的综述实验性文章

1 INTRODUCTION

1.1 Motivation

1. 作者的初衷是把不同领域（比如机器学习ML，多媒体MM，数据库DB，工业界）的能解决同一个问题（近似NN，ANNS）的方法拿出来，进行比较。
2. ANNS算法可以由多个层面去衡量：

• 搜索时间复杂度；
• 搜索质量；
• 索引大小；
• 可扩展性（数据量、维度）；
• 鲁棒性；
• 可更新性；
• 调优参数是否方便；
  目前大多数实验用的query workload和数据集的数据分布式是一致的，这会有失偏颇。

3. 目前各种实验里的结果有很多是矛盾的，虽然可以归因于实验设置不同，但是缺乏统一的比较，作者来做这件事。

2 BACKGROUND

2.1 Problem Definition

d维向量，距离是欧式距离。

3 RELATED WORK

3.1 Hashing-based Methods

3.1.1 Locality Sensitive Hashing(LSH)

和数据分布无关的哈希。依靠一组局部敏感的哈希函数，把邻近的数据点哈希更大概率到同一个哈希码上。
构建多个哈希表，根据碰撞确定KNN。
哈希函数是LSH方法的关键，有静态的符合哈希函数，也有动态的碰撞技术策略。

3.1.2 Learning to Hash (L2H)

根据数据分布确定哈希函数。
相似性维持（similarity-preserving）是L2H方法的关键。在原来的向量空间相似，在哈希码空间上也要尽量相似。
L2H方法可以分为几类：

• 成对相似性维持；
• 成组相似性维持；
• 隐式相似性维持；
• 量化的（最小化量化变形）；
  现在也有用深度神经网络来学习哈希函数的。本文不给数据做label，因此只采用无监督学习。

3.2 Partition-based Methods

分区的方法主要是将多维空间分成若干个不相交的区域，查询时首先定位到Query所属的区域，然后在该区域及其附近搜索KNN。
分区方法主要分为三类：

• Pivoting：选几个点做pivots，然后其它点根据与Pivot的距离进行分区；递归进行操作，比如VP-Tree
• Compact：基于聚类进行分区；
• hyperplane(超平面)：暂时没看懂

3.3 Graph-based Methods

图的方法是构造一个邻近图，每个数据点作为一个顶点，边来描述数据点之间的临近关系。遵循的原则就是：邻居的邻居大概率也是我的邻居。主要也分为两类。

• KNN图：每个顶点保留K条边，作为KNN的邻居结果；
• NSW图：称为导向性的小世界图。现在还有多级的NSW图，是效果最好的方法之一。

4 DIVERSIFIED PROXIMITY GRAPH

作者这个综述做着做着，从实验分析中得到了一些insights，于是自己动手做了改进，就是这个DPG。

4.1 Motivation

DPG是根据KNN图改编的。

• 考虑下面这张2-NN图，如果按照距离来看，关于p最近的两个点a3,a4将成为p指向的邻居，但是其实指向他们意义不大，因为它们本来就是一个cluster里的，搜索的时候肯定会相互搜到，因此在KNN list里面浪费一个名额；不如去选一个“角度”差的比较大的b，这样可以搜到更丰富的邻居。这就是名称diversified的由来。

• 另一方面，根据高维空间中Hubness的发现，高维空间中很大比例的数据点不会成为别的点备选的KNN，为了拯救这些点，提升丰富度，DPG采用双向边。

  
  image.png

4.2 Diversified Proximity Graph

至于这个图的构建过程也比较简单，从原来的每个节点的KNN list里面，筛选出r个点，要求这个r个点成对之间的平均夹角是最大的（diversified），让p和这r个点双向连接。
具体于这r个点是怎么选的，首先选一个起始点，然后按照贪心选择从list里面选一个可以使得平均角度最大的点。
经过实验，r一般为K的一半效果最好。

5 EXPERIMENTS

【未完待续】