标题：高维数据近似NN搜索-实验、分析、优化
这是一篇针对广义KNN算法的综述实验性文章
1 INTRODUCTION
1.1 Motivation
- 作者的初衷是把不同领域（比如机器学习ML，多媒体MM，数据库DB，工业界）的能解决同一个问题（近似NN，ANNS）的方法拿出来，进行比较。
- ANNS算法可以由多个层面去衡量：
- 搜索时间复杂度；
- 搜索质量；
- 索引大小；
- 可扩展性（数据量、维度）；
- 鲁棒性；
- 可更新性；
- 调优参数是否方便；
目前大多数实验用的query workload和数据集的数据分布式是一致的，这会有失偏颇。
- 目前各种实验里的结果有很多是矛盾的，虽然可以归因于实验设置不同，但是缺乏统一的比较，作者来做这件事。
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
【未完待续】
