编者的总结

• 通过LSB-trees找图的入口点，图就可以构造的简单点。这和去年的HVS (VLDB) 思想上比较像。
• 因为删去了有效剪枝，所以索引大小偏大，但构建时间提升了一些。
• 构造了代价模型。

编者的思考

• 技术深度相对有限，组合起来了LSH和APG，但提供了概率保障。

ABSTRACT

• LSH的方法有边界问题，很难达到高质量结果
• 图的方法构建速度太慢，很难增量维护
• 本文将二者结合，用一个轻量化的LSH框架构建图，称为LSH-APG
  • LSH-APG通过连续插入构建，基于LSH的高效搜索
  • 首先通过LSH找到高质量的入口点，然后进一步用图方法搜索；
  • 另有一个剪枝方法可以加速计算
  • 支持增量维护，插入和删除代价几乎和数据集基数无关
  • 提供一个代价模型，证明查询代价几乎和数据集基数无关

4 LSH-APG FRAMEWORK

4.1 Naive-APG: the Basic Structure

图的构建使用的是最简单，最快速的图。边的出度范围为[T,T']，按照插入的方式构建：

• efConstructuion = T
• 有反向边插入，但是如果反向邻居度数超过T'，只需要剔除距离最远的。

• T'一般选择为2T

  
  
  image.png

4.2 LSH-APG: Optimized by LSH Indexes

• 这样naive的图查询质量肯定很差，而且注意到构建也是通过查询插入的，这也会导致插入代价很高。针对这个问题，作者把图套上了LSH框架。

• LSH的方法也不难，而且也不需要很高的精度，因为后续会接上图来保证精度，具体来说：

  1. 对每一个插入点用K个哈希函数转换成一个K维向量；
  2. 用z-order curve转化成单维可排序的；
  3. 插入到B+-tree里面去；
  4. 重复L次，生成L棵B+-tree。

• 哈希函数很简单：

  
  
  image.png

• a的各个维度是独立同分布的，从标准正态分布抽出来的

  
  
  image.png

• w是预定义的整数值，b是从均分分布[0,w)随机抽出来的实数。

• 构造算法只需要简单改造即可构建出LSB树

  
  
  image.png

4.3 ANN Query in LSH-APG

• 查询算法仍不复杂，是LSH方法和图方法的结合。

1. 通过LSB-tree，拿到近似KNN，作为图的entry points和initial candidate set (EP)。
2. 依次出队EP，如果比当前BSF要差，中止掉。

3. 否则在图上探测它的每个未访问过的邻居，首先用LSH的方案进行剪枝，若剪枝通过，计算真实距离加入EP和BSF。

   
   
   image.png

4.4 Cost Model of LSH-APG

5 LSH-BASED PRUNING CONDITION

6 INDEX MAINTENANCE

提供了一个删除算法，可以避免扫表来找删除点的入边，但是不能找到所有的入边。

7 EXPERIMENTAL STUDY

Ubuntu server with 4 Intel(R) Xeon(R) Gold 6218 CPUs (160 threads) and 1.5 TB RAM

• 索引并行构建（openMP）
• 线性查询

7.1 Experimental Settings

• Query: 随机选100条，然后从数据集中移出去；

• k=50, 即50-nn

  
  
  image.png
• 参数：统一一套参数
  • LSH-APG： K = 16, L = 2,T = 24,T ′ = 2T , pτ = 0.95
  • HNSW：M=48，efconstruction=80
  • NSG: L=40, R=50, C=500
  • HCNNG: 500个Cluster，10次聚类
  • DB-LSH：c = 1.5, K = 12, L = 5

7.2 Self Evaluation

7.2.1 Evaluation of the LSH framework

有无LSH的消融实验，上图查询，下图构建：

• 在100M的数据集上查询性能差距比较明显，在1M上差距不明显

• 构建效率方面LSH作用比较明显，作者说构建出图基本是一样的，说明Naive-APG的Efconstruction需要很大，不然图的质量应该不行。

  
  
  image.png

7.2.2 Parameter study on L and K

在Deep1M上做的实验

• L对于Recall的影响几乎没有，毕竟只决定了起始点；

• L对查询时间影响较大，但不清楚L=0代表什么，L>1的效果也不显著

  
  
  image.png
• K太大会减少LSH索引返回结果的个数（碰撞概率更低），太小精度不够，因此：

  • K过大会Recall降低，但entry point质量在上升，所以查询时间一直在变快。

    
    
    image.png

7.2.3 Parameter study on pτ

在SIFT100M上做的实验

• pτ越小，剪枝越强，但由于概率的问题，recall也下降了。

• 整体感觉用处不大。

  
  
  image.png

7.2.4 Parameter study on T and T'

image.png

7.3 Evaluation of Indexing Performance

• LSH-APG因为缺乏有效的剪枝，所以index是最大的。不过LSH的部分并不大。

  
  
  image.png

• index time提升也不算大。Gauss和Rand两个提升最大的合成数据集比较少见。

  
  
  image.png

7.4 Evaluation of Query Performance

7.4.1 Effect of n

在SIFT100M上做的实验

• 从20m-100m，伸缩性还不错，不知道拟合结果是什么复杂度。

  
  
  image.png

7.4.2 Effect of k

在SIFT100M上做的实验

image.png

7.4.3 Effect of d

image.png

7.4.4 Recall-QT Curve

• 提升还可以，数据集有点少

  
  
  image.png

7.5 Evaluation of Updating

批量增删，且无比较

image.png