原文章

$\text{0. }$写在前面

$\text{0.1. }$一些预备知识

1️⃣最邻近查询

1. 精确最邻近查询：从数据库中找到与查询对象最近的对象
   • 最邻近($\text{NNS}$)：与查询点最近的唯一点
   • $k\text{-}$最邻近($\text{k-NNS}$)：与查询点距离最近的$k$个点
2. 近似最邻近查询：
   • 是啥：最邻近查询的$\text{Recall<100\%}$版本，即$\text{ANNS/k-ANNS}$
   • 原由：高维空间找到精确最邻近很难(突破暴力解法)，即所谓维度诅咒(灾难)
3. $\text{(r,c)-ANN}$：给定距离阈值$r$/查询点$q$，考虑数据库点$e_i$在$q$周围$r$以及$cr$范围的分布
   

   $\text{Case}$	$\exists e_i使\text{D}\in [0,r]$	$\exists e_i使\text{D}\in [r,cr]$	$\exists e_i使\text{D}\in [cr,\infty ]$	返回对象
   $\text{Case 1}$	一定	可能	可能	满足$D\le cr$的$e_i$
   $\text{Case 2}$	不可能	不可能	不可能	寂寞
   $\text{Case 3}$	不可能	一定	可能	满足$D\le cr$的$e_i$

   • 表中$\text{D=}\text{dist}(q,e_i)$
   • 该问题主要应用在基于$\text{LSH}$的方法中

2️⃣关于$k\text{-Mean}$算法：

1. 什么是$k\text{-Mean}$：将空间分为$\text{k}$个尽可能内部紧凑/互相远离的部分，分为以下两个阶段
   • 数据分配：将每个数据点分给最近的聚类中心，复杂度为$O(nk)$
   • 重置中心点：重新计算每个聚类的中心点，复杂度为$O(n)$
2. 关于$k\text{-Mean}$的大聚类数目
   • 是什么：在进行聚类时，选取$k$等于一个很大的数，以至于达到$\Theta (n)$规模
   • 为何不能$k\text{=}\Theta (n)$：数据分配复杂度为$O(nk)\text{=}O(n^2)$，查询(计算与$k$个中心距离)为$O(n)$
   • 关于如何规避$k\text{=}\Theta (n)$则见后续$\text{FLANN}/\text{Annoy}/\text{OPQ}$

$\text{0.2. }$本文的主要研究

1️⃣在不同领域的数据集上对比不同领域的$\text{ANN}$算法

1. 当前问题：一些$\text{ANN}$的提出只针对特定领域，且只在特定领域的数据集上测试
2. 本文工作：选取不同领域的多个最先进算法，在不同领域的多个数据集上测试

2️⃣评估了算法在多种设置和指标下的性能

1. 性能类：搜索的时间复杂度，搜索质量(精确度/正确率)
2. 资源类：索引大小
3. 耐草类：可扩展性，鲁棒性
4. 维护类：可更新性，更新参数的成本

3️⃣设计了一种改进新基于图的算法$\text{DPG}$

$\text{0.3. }$本文一些研究限制

1️⃣算法选择：只选择当前最先进的算法，排除被明显超过的其它算法

2️⃣算法实现：注重算法技术本身，削弱实现时的优化 (如取消多线程/多$\text{CPU}$等)

3️⃣密集向量：默认向量都密集，不考虑对稀疏数据的特殊处理

4️⃣标签：将每个点的真实$k$个最邻近点作为标签，以便得到召回率

$\text{1. }$ 三大类$\text{ANN}$算法回顾以及$\text{DPG}$

$\text{1.1. }$基于哈希的：高维数据$\to$低维哈希码

$\text{1.1.1. LSH}$：有理论保证

1️⃣$\text{LSH}$原理：当对于$e_i,e_j$哈希函数的选择是随机和独立的($\text{CIKM’13}$)，则以下

输入点$e_i,e_j$	$\stackrel{局部敏感哈希函数}{\to }$	映射结果
相似度高，即$\text{dist}(e_i,e_j)<r$	$\stackrel{局部敏感哈希函数}{\to }$	高概率被映射到相同哈希码上
相似度低，即$\text{dist}(e_i,e_j)>cr$	$\stackrel{局部敏感哈希函数}{\to }$	高概率被映射到不同哈希码上

2️⃣$\text{LSH}$函数：影响性能的关键

1. 针对欧几里得空间的：$\text{SCG’04}$ / $\text{FOCS’06}$ / $\text{SODA’14}$ / $\text{WADS’07}$ / $\text{STOC’15}$
2. 基于随机线性投影的：$\text{SCG’04}$ / $\text{VLDB’99}$ / $\text{SODA’06}$ / $\text{SIGMOD’09}$

3️⃣$\text{LSH}$函数及$\text{LSH}$方法的改进研究

1. $\text{LSH}$函数的连接：将多个哈希函数首尾相连，但增加了哈希表数量(时空开销)
2. 动态$\text{LSH}$函数
   • 静态$\text{LSH}$原理：处理所有点构建哈希表$\to$哈希表一构建就不变$\to$执行查询
   • 静态$\text{LSH}$弊端：哈希表随机构建，会导致与查询点很近的点与查询点不碰撞(被忽略)
   • 动态$\text{LSH}$：查询时动态地计数和调整碰撞情况，$\text{VLDB’07}$ / $\text{SIGMOD’07}$ / $\text{SIGMOD’16}$
3. 启发式寻桶
   • 咋办：通过启发式方法(靠直觉)检查查询点附近的其它桶，$\text{VLDB’07}$ / $\text{MM’08}$ / $\text{VLDB’07}$
   • 好处：提高搜索质量同时，不增加哈希表数量(相比连接$\text{LSH}$函数)

$\text{1.1.2. Learning to Hash(L2H)}$：无理论保证

1️⃣原理：学习原有数据的分布$\stackrel{生成}{\to }$特定哈希，使得原空间中的近似关系在哈希空间得到保留

2️⃣类型：

$\text{Type}$	$\text{Pub.}$
成对相似性保持类	$\text{ICML’11}$ / $\text{NIPS’08}$ / $\text{NIPS’14}$ / $\text{KDD’10}$ / $\text{CVPR’13}$
多重相似性保持类	$\text{ICCV’13}$ / $\text{MM’13}$
隐式相似性保持类	$\text{CVPR’11}$ / $\text{ICCV’13}$
量化类	$\text{TPAMI’11}$ / $\text{TPAMI’13}$ / $\text{NIPS’12}$

3️⃣关于量化类方法：最有效的$\text{L2H}$方法

1. 核心：最小化量化失真 (及 $\min \sum$ 每个数据点$\leftrightarrow$其最邻近指的差)
2. $\text{PQ(Product Quantization)}$算法，$\text{TPAMI’11}$ / $\text{TIT’06}$($\text{Quantization}$)
   • 原理：$\text{M}$维原始向量$\stackrel{分割}{\to }$$\text{N}$个$\frac{\text{M}}{\text{N}}$维子向量$\underset{(寻求每个子向量最近的质心\text{Index})}{\overset{向量量化}{\to }}$$\text{N}$维短代码(向量)
   • 改善途径：

     $\text{Type}$	$\text{Pub.}$
     改善$\text{PQ}$的索引步骤	$\text{TPAMI’13}$ / $\text{CVPR’13}$ / $\text{CVPR’15}$ / $\text{ICCV’13}$ / $\text{CVPR’14}$
     改善$\text{PQ}$的搜索步骤	$\text{CVPR’14}$ / $\text{CVPR’12}$ / $\text{ICASSP’11}$ / $\text{CVPR’16}$

   • 扩展$\text{PQ}$算法：优化$\text{PQ}$($\text{CVPR’14}$)，加性量化($\text{CVPR’14}$)，复合量化($\text{ICML’14}$)

4️⃣基于神经网络的(无监督)哈希方法

1. Semantic哈希：
   • 原理：构建多层$\text{RBM(Restricted Boltzmann Machines)}$
   • 目标：为文本(文档)学习紧凑的二进制代码
2. 如何学习二进制代码
   • 通过生成二进制代码：

     $\text{Type}$	$\text{Pub.}$
     设计符号激活层以	$\text{CVPR’16}$ / $\text{CVPR’15}$ / $\text{IJCAI’17}$ / $\text{TIP’17}$
     提出了约束倒数第二层	$\text{ECCV’16}$

   • 通过重构数据：使用自编码器作为隐藏层，$\text{CVPR’15}$ / $\text{IPTA’17}$
3. 二进制约束的优化问题
   • 成因：必须从哈希函数的输出获得二进制代码，是一个$\text{NP-Hard}$问题
   • 优化：由$\text{relaxation+rounding}$法使二进制代码次优，如离散优化$\text{NIPS’14}$ / $\text{TPAMI’18}$

$\text{1.2. }$基于划分的方法

1️⃣原理：

1. 构建：将整个高维空间(递归式)划分为多个不相交的区域
2. 核心：默认如果$q$在$r_q$内，则$q$的最邻近也在$r_q$(或其附近)

2️⃣空间的划分方式

1. 枢轴法($\text{pivoting}$)：
   • 根据点$\text{-}$轴距来划分点：$\text{VP-Tree}$($\text{SODA’93}$) / $\text{Ball Tree}$($\text{ICML’08}$)
2. 超平面法($\text{hyperplane}$)：
   • 随机方向的超平面：随机投影树($\text{STOC’08}$)
   • 轴对齐的分离超平面：随机$\text{KD}$树($\text{CVPR’08}$/$\text{TPAMI’14}$)
3. 紧凑法($\text{compact}$)：
   • 将数据划分为簇：$\text{T-C’75}$
   • 创建$\text{Voronoi}$划分：$\text{SPIRE’99}$ / $\text{ICML’06}$

$\text{1.3. }$基于图的方法

1️⃣原理：

1. 构建：数据$\stackrel{对应}{\leftrightarrow }$图结点$+$数据邻近关系$\stackrel{对应}{\leftrightarrow }$图边$\stackrel{组成}{\to }$邻近图
2. 核心：默认邻居的邻居也是邻居
3. 方法：通过迭代扩展邻居的邻居$+$遵循边的最佳优先搜索策略

2️⃣第一大类：构建近似$\text{KNN-Graph}$，图中每个节点指向最近的$k$个邻居

1. 在高维空间的应用：$\text{IJCAI’11}$ / $\text{CVPR’12}$ / $\text{CoRR’17}$ / $\text{WWW’11}$
2. 关于算法初始点：
   • 随机初始点：容易陷入局部最优，$\text{ComACM’80}$
   • 改进工作：让$\text{LSH}$($\text{TCYB’14}$) / 随机$\text{KD}$树($\text{CoRR’16}$)生成初始点

3️⃣第二大类：$\text{SW(Small-World)-Graph}$，图中任两节点可较少步到达 ($\text{Nature’20}$)

1. $\text{NSW}$方法：通过迭代插入点来构建$\text{SW-Graph}$ ($\text{IS’14}$)
2. $\text{HNSW}$方法：$\text{NSW}$的扩展，最有效的$\text{ANNS}$算法之一 ($\text{CoRR’16}$)

$\text{1.4. }$关于$\text{DPG}$

$\text{1.4.1. }$传统$\text{KNN}$图：连通性较差

1️⃣原因之一：最邻近聚集在一个方向

1. 实例：如下$\text{2-NN}$图中，搜索路径只能 p → { a 3 , a 4 } p\text{→}\{a_3,a_4\} p→{a3​,a4​}而不能$p\text{→}b$即使$p\leftrightarrow b$很近
   
2. 咋整：选取邻居时不仅考虑距离，还需考虑角度

2️⃣原因之二：中心性问题

1. 是啥：$\text{KNN}$图中很多的点没有入度，即不作为其他点的最邻近($\text{JMLR’11}$)，如上图点$p$
2. 咋整：将单向边变成双向边

$\text{1.4.2. DPG}$

1️⃣相似度：给定$p$及其$K$最邻近列表$\mathcal{L}$，对于$x,y\in \mathcal{L}$用角度$\theta (x,y)\text{=}\angle xpy$衡量$xy$的相似度

2️⃣$\text{DPG}$的构建算法：

1. 算法流程
   • 对于$p$，先找出其$K$个最邻近点(组成$\mathcal{L}$列表)
   • 从$\mathcal{L}$列表中选择子集$\mathcal{S}$($\text{|}\mathcal{S}\text{|=}\kappa$)使$\mathcal{S}$中两点平均角度最大；选择方法遵循以下贪婪启发式算法
     
   • 将所有边双向化，即$\forall u\in \mathcal{S}$将$(p,u)$与$(u,p)$都包括在邻近图中
2. 关于构建算法
   • 时间复杂度为$O\left({\kappa }^{2}Kn\right)$，本文也实现了一个简化的性能较差版本复杂度为$O\left(K^{2}n\right)$
   • 为$\text{|}\mathcal{S}\text{|=}\kappa$选取$K$至关重要，实证表明$K\text{=}2\kappa$最佳

3️⃣搜索过程：与$\text{KGraph}$的搜索完全相同

$\text{2. }$实验前

$\text{2.1. }$参与实验的算法

1️⃣基于$\text{LSH}$：$\text{QALSH}$($\text{VLDB’15}$)，$\text{SRS}$($\text{VLDB’14}$)，$\text{FALCONN}$($\text{NIPS’15}$)

2️⃣基于$\text{L2H}$：

算法类型	算法
基于二进制	$\text{SGH}$($\text{IJCAI’15}$)，$\text{AGH}$($\text{ICML’11}$)，$\text{NSH}$($\text{VLDB’15}$)
基于量化	$\text{OPQ}$($\text{TPAMI’14}$)，$\text{CQ}$($\text{ICML’14}$)
其它	$\text{SH}$($\text{SIGKDD’15}$)，$\text{NAPP}$($\text{VLDB’15}$)

3️⃣基于划分的：

1. $\text{FLANN}$类：$\text{FLANN/FLANN-HKM/FLANN-KD}$($\text{TPAMI’14}$)，$\text{Annoy}$
2. $\text{VP}$树($\text{TPAMI’14}$)

4️⃣基于图的：

算法类型	算法
基于小世界的	$\text{SW}$($\text{IJCAI’15}$)，$\text{HNSW}$($\text{CoRR’16}$)
基于$\text{KNN}$图	$\text{KGraph}$($\text{WWW’11}$)，$\text{DPG}$(本文)
基于树	$\text{RCT}$($\text{TPAMI’15}$)

$\text{2.2. }$数据集与查询负载

1️⃣数据集概述：$\text{18}$个真实数据集(图像/音频/视频/文本)$+$$\text{2}$个合成($\text{Synthetic}$)数据集

$\begin{array}{cccccc}\text{ Name }& n\left(\times 10^3\right)& d& \text{ RC }& \text{ LID }& \text{ Type }\\ {\text{ Nus }}^{\ast }& 269& 500& 1.67& 24.5& \text{ Image }\\ {\text{ Gist }}^{\ast }& 983& 960& 1.94& 18.9& \text{ Image }\\ {\text{ Rand }}^{\ast }& 1,000& 100& 3.05& 58.7& \text{ Synthetic }\\ {\text{ Glove }}^{\ast }& 1,192& 100& 1.82& 20.0& \text{ Text }\\ \text{ .... }& ....& ....& ....& ....& \text{ .... }\end{array}$

2️⃣度量数据集难度的指标

1. 相对对比度($\text{RC}$)：
   • 计算：$\text{RC=}\frac{\text{每两点距离的平均}}{\text{每点与其最邻近距离的平均}}$
   • 含义：较小的$\text{RC}$会导致最邻近不易区分，导致搜索难度变大
2. 局部内在维度($\text{LID}$)：数据集在某个局部区域的内在维度，越高意味着结构越复杂难以查询

3️⃣查询负载

1. 对每个数据集：从每个数据集中移出$\text{200}$个点作为查询点
2. 对于$\text{k-NN}$图算法：进行性能测试时，默认$\text{k=20}$

$\text{2.3. }$实验设置

2️⃣测试配置

1. 选择并使用来自$\text{NMSLIB}$库中已经实现的几种算法($\text{NAPP/VP-Tree/SW/HNSW}$)
   • $\text{NMSLIB}$库：专用于非度量空间的开源库，实现并提供了诸多高维相似性搜索算法
   • 度量空间：距离计算具备传统的几何性质，比如欧几里得空间
2. 仔细调整了每个算法的超参数
3. 关闭了特定的硬件优化，比如禁用$\text{KGraph}$的多线程等

3️⃣环境：

1. 系统：$\text{Linux}$服务器
2. 计算：$\text{Intel Xeon e5-2690}+\text{32G RAM}$
3. 编译：$\text{C}$++由$\text{g}$++$\text{4.7}$编译，$\text{MATLAB}$由$\text{MATLAB 8.5}$编译

$\text{2.4. }$评估指标

1️⃣查询精度指标：运行算法找到$\text{N}$个候选最邻近，将$\text{N}$点按离查询点的距离排序，引出以下指标

1. 基础指标：

   指标	含义
   $\text{Recall}$	$\frac{\text{N}个候选项目中真实最邻近的数目}{\text{k}}$
   $\text{Precision}$	$\frac{\text{N}个候选项目中真实最邻近的数目}{\text{k}}$
   $\text{F1 Score}$	$2\text{×}\frac{\text{Precision+Recall}}{\text{Precision+Recall}}$

2. $\text{AP(Average Precision)}=\frac{\sum _{i=1}^{\text{N}}[\text{P(i)×Rel(i)}]}{\text{N}中真实最邻近数量}$
   • 位置参数$i$：介于$\text{1→N}$间用于标记候选点，$i\text{=}1$表示距离查询点最近，$i\text{=}\text{N}$表示最远
   • 相关性标记：将候选$\text{N}$个最邻近点中，真实的最邻近点标记为相关记作$\text{Rel(i)=1}$
   • 精确率：定义为$\text{P(i)=}\frac{截至位置i时,最邻近的数目}{i}$
   • $\text{mAP}$：就是所有查询点的$\text{AP}$的平均，本文采用此指标
3. $\text{Accuracy}=\sum _{i=0}^k\frac{\text{dist(q, kANN(q)[i])}}{\text{dist(q, kNN(q)[i])}}$参数含义如下，越接近$1$表示最邻近查找越精准
   • $\text{dist(q, kANN(q)[i])}$：查询点$\stackrel{距离}{\leftrightarrow }$使用某个$\text{ANN}$算法排序后第$i$个最邻近点
   • $\text{dist(q, kNN(q)[i])}$：查询点$\stackrel{距离}{\leftrightarrow }$真实的第$i$个最邻近点

2️⃣查询效率(时间)指标：

1. 加速比$\frac{\bar{t}}{t^{\prime }}$：即查询时间比上线性暴力扫描的时间
2. 文中还提到了，除了基于图的算法，都可以用调整$\text{N}$的方法调整查询指标

3️⃣其它指标：

1. 索引指标：索引构建时间，索引大小，索引内存
2. 可扩展性

$\text{3. }$实验

$\text{3.1. }$第一轮：类别内评估

1️⃣评估工作：

1. 评估流程：
   • 将所有算法置于$\text{Sift/Notre}$数据集上测试
   • 权衡查询速度/召回的$\text{Trade Off}$，以从每个类别中选出算法进行下一轮评估
2. 评估标准：
   • 认为相同召回率下速度提升更大的为更优
   • 对于算法数据存在外部的($\text{IO}$次数决定速度)，故将总页数/搜索时访问页数作为速率提升

2️⃣评估结果：进入第二轮实验的算法

类别	评估选取的结果
$\text{LSH}$类	$\text{SRS/QALSH}$间选取$\text{SRS}$，$\text{FALCONN}$在$\text{L2}$距离下性能缺乏保证故放第二轮
$\text{L2H}$类	选取$\text{OPQ}$
空间分割类	排除$\text{VP-Tree}$
基于图类	选取$\text{KGraph}$和$\text{HNSW}$，$\text{DPG}$延后到下一轮

$\text{3.2. }$第二轮评估

$\text{3.2.1. }$对查询质量/事件的评估

1️⃣加速比$@\text{Recall=0.8}+\text{Recall}@$加速比$\text{=50}$:

1. $\text{DPG}$和$\text{HNSW}$性能最佳
2. 其中$\text{DPG}$对$\text{KGraph}$的改良显著，尤其在难数据集上
3. $\text{SRS}$及其拉跨，源于其没有利用数据集的分布

2️⃣加速比$@\text{Recall=0→1}$

1. $\text{HNSW/KGraph/Annoy}$整体性能优越
2. $\text{DPG/KGraph}$在高$\text{Recall}$下性能优越，但整体不如$\text{HNSW}$等

3️⃣$\text{Recall}@$访问数据比$\text{=}0\%\text{→}100\%$

1. 除$\text{HNSW}$外基于图的算法在百分比低时拉跨，源于其算法入口点随机
2. $\text{HNSW}$的分层结构中每层入口不随机，所以性能保持优越

4️⃣$\text{Accuracy}@$$\text{Recall}\text{=}0\text{→}1$：专为$\text{c-ANN}$设计的$\text{SRS}$和$\text{FLACONN}$性能优越

$\text{3.2.2. }$ 对索引空间的评估

1️⃣$\frac{\text{index size}}{\text{data size}}$的评估

1. 索引大小规模
   • 最大：$\text{Annoy}$(大于数据大小)，源于其需要维护数量庞大的$\text{Tree}$结构
   • 最小：$\text{OPQ/SRS}$
2. 索引大小与维度无关：$\text{DPG/KGraph/HNSW/SRS/FLACONN}$
3. 索引大小剧烈变化：$\text{FLANN}$，源于其有三种不同索引结构供选择

2️⃣索引构建时间

1. 索引时间最小：$\text{FALCOMNN}$，其次是$\text{SRS}$
2. 索引时间与维度无关：$\text{OPQ}$，源于其涉及子码字的计算
3. 相比于$\text{DPG/KGraph}$，$\text{DPG}$在图的多样化构建上没花太多额外时间

3️⃣索引内存成本：$\text{OPO}$在索引构建时内存开销低，由此在大规模数集上高效

$\text{4. }$试验后

$\text{4.1. }$算法选择策略

1️⃣计算/主存足够时：选择$\text{DPG/HNSW}$，其次选$\text{Annoy}$以在硬件和搜索性能上折中

2️⃣看重索引构建时间时：选择$\text{FALCONN}$

3️⃣处理大规模数据：$\text{OPQ/SRS}$，源于二者内存成本/构建时间较小

$\text{4.2. }$进一步分析：空间划分类算法

1️⃣$k\text{-Mean}$类的$\text{ANN}$算法：如何规避$k\text{=}\Theta (n)$

1. $\text{FLANN}/\text{Annoy}$(递归树思想)：每个结点将数据划为$k$块(子节点)直到叶节点
   • 二者在基于划分的算法中性能最佳
   • $\text{FLANN}$在大多情况下选择$\text{FLANN-HKM}$(层次$k\text{-Mean}$)
2. $\text{OPQ}$(子空间划分思想)：将整体分为$\text{M}$块$\to$每块中进行$k^{\prime }\text{-Mean}$($k^{\prime }$较小)$\to$组合每块聚类结果
3. 实验证明：在$\text{Audio}$类型数据上，除了使用$k\text{-Means}$的暴力方法，$\text{FLANN-HKM}$($\text{L=2}$)最好
   

2️⃣进一步实验证明：多层次$k\text{-Means}$树的$\text{FLANN-HKM}$(类似$\text{Annoy}$)不能提高性能

$\text{4.3. }$进一步分析：图类算法

1️⃣为何基于图的算法($\text{KGraph/DPG/HNSW}$)表现好

1. 图结构上：高连通性$+$全局可达性
2. 搜索算法上：得益于高连通性，算法可沿边逼近最邻近$+$存在多条路径(避免局部最优)

2️⃣$\text{KGraph}$在部分数据集上不佳：算法入口点随机$+$缺乏跨聚类的