编者的总结
- 通过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的方法也不难，而且也不需要很高的精度，因为后续会接上图来保证精度，具体来说：
- 对每一个插入点用K个哈希函数转换成一个K维向量；
- 用z-order curve转化成单维可排序的；
- 插入到B+-tree里面去；
- 重复L次，生成L棵B+-tree。
-
哈希函数很简单：
image.png -
a的各个维度是独立同分布的，从标准正态分布抽出来的
image.png w是预定义的整数值，b是从均分分布[0,w)随机抽出来的实数。
-
构造算法只需要简单改造即可构建出LSB树
image.png
4.3 ANN Query in LSH-APG
- 查询算法仍不复杂，是LSH方法和图方法的结合。
- 通过LSB-tree，拿到近似KNN，作为图的entry points和initial candidate set (EP)。
- 依次出队EP，如果比当前BSF要差，中止掉。
-
否则在图上探测它的每个未访问过的邻居，首先用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'
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上做的实验
7.4.3 Effect of d
7.4.4 Recall-QT Curve
-
提升还可以，数据集有点少
image.png
7.5 Evaluation of Updating
批量增删，且无比较
