編者的總結(jié)

• 通過LSB-trees找圖的入口點，圖就可以構(gòu)造的簡單點。這和去年的HVS (VLDB) 思想上比較像。
• 因為刪去了有效剪枝，所以索引大小偏大，但構(gòu)建時間提升了一些。
• 構(gòu)造了代價模型。

編者的思考

• 技術(shù)深度相對有限，組合起來了LSH和APG，但提供了概率保障。

ABSTRACT

• LSH的方法有邊界問題，很難達(dá)到高質(zhì)量結(jié)果
• 圖的方法構(gòu)建速度太慢，很難增量維護(hù)
• 本文將二者結(jié)合，用一個輕量化的LSH框架構(gòu)建圖，稱為LSH-APG
  • LSH-APG通過連續(xù)插入構(gòu)建，基于LSH的高效搜索
  • 首先通過LSH找到高質(zhì)量的入口點，然后進(jìn)一步用圖方法搜索；
  • 另有一個剪枝方法可以加速計算
  • 支持增量維護(hù)，插入和刪除代價幾乎和數(shù)據(jù)集基數(shù)無關(guān)
  • 提供一個代價模型，證明查詢代價幾乎和數(shù)據(jù)集基數(shù)無關(guān)

4 LSH-APG FRAMEWORK

4.1 Naive-APG: the Basic Structure

圖的構(gòu)建使用的是最簡單，最快速的圖。邊的出度范圍為[T,T']，按照插入的方式構(gòu)建：

• efConstructuion = T
• 有反向邊插入，但是如果反向鄰居度數(shù)超過T'，只需要剔除距離最遠(yuǎn)的。

• T'一般選擇為2T

  
  
  image.png

4.2 LSH-APG: Optimized by LSH Indexes

• 這樣naive的圖查詢質(zhì)量肯定很差，而且注意到構(gòu)建也是通過查詢插入的，這也會導(dǎo)致插入代價很高。針對這個問題，作者把圖套上了LSH框架。

• LSH的方法也不難，而且也不需要很高的精度，因為后續(xù)會接上圖來保證精度，具體來說：

  1. 對每一個插入點用K個哈希函數(shù)轉(zhuǎn)換成一個K維向量；
  2. 用z-order curve轉(zhuǎn)化成單維可排序的；
  3. 插入到B+-tree里面去；
  4. 重復(fù)L次，生成L棵B+-tree。

• 哈希函數(shù)很簡單：

  
  
  image.png

• a的各個維度是獨立同分布的，從標(biāo)準(zhǔn)正態(tài)分布抽出來的

  
  
  image.png

• w是預(yù)定義的整數(shù)值，b是從均分分布[0,w)隨機(jī)抽出來的實數(shù)。

• 構(gòu)造算法只需要簡單改造即可構(gòu)建出LSB樹

  
  
  image.png

4.3 ANN Query in LSH-APG

• 查詢算法仍不復(fù)雜，是LSH方法和圖方法的結(jié)合。

1. 通過LSB-tree，拿到近似KNN，作為圖的entry points和initial candidate set (EP)。
2. 依次出隊EP，如果比當(dāng)前BSF要差，中止掉。

3. 否則在圖上探測它的每個未訪問過的鄰居，首先用LSH的方案進(jìn)行剪枝，若剪枝通過，計算真實距離加入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

• 索引并行構(gòu)建（openMP）
• 線性查詢

7.1 Experimental Settings

• Query: 隨機(jī)選100條，然后從數(shù)據(jù)集中移出去；

• k=50, 即50-nn

  
  
  image.png
• 參數(shù)：統(tǒng)一一套參數(shù)
  • 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的消融實驗，上圖查詢，下圖構(gòu)建：

• 在100M的數(shù)據(jù)集上查詢性能差距比較明顯，在1M上差距不明顯

• 構(gòu)建效率方面LSH作用比較明顯，作者說構(gòu)建出圖基本是一樣的，說明Naive-APG的Efconstruction需要很大，不然圖的質(zhì)量應(yīng)該不行。

  
  
  image.png

7.2.2 Parameter study on L and K

在Deep1M上做的實驗

• L對于Recall的影響幾乎沒有，畢竟只決定了起始點；

• L對查詢時間影響較大，但不清楚L=0代表什么，L>1的效果也不顯著

  
  
  image.png
• K太大會減少LSH索引返回結(jié)果的個數(shù)（碰撞概率更低），太小精度不夠，因此：

  • K過大會Recall降低，但entry point質(zhì)量在上升，所以查詢時間一直在變快。

    
    
    image.png

7.2.3 Parameter study on pτ

在SIFT100M上做的實驗

• pτ越小，剪枝越強(qiáng)，但由于概率的問題，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兩個提升最大的合成數(shù)據(jù)集比較少見。

  
  
  image.png

7.4 Evaluation of Query Performance

7.4.1 Effect of n

在SIFT100M上做的實驗

• 從20m-100m，伸縮性還不錯，不知道擬合結(jié)果是什么復(fù)雜度。

  
  
  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

• 提升還可以，數(shù)據(jù)集有點少

  
  
  image.png

7.5 Evaluation of Updating

批量增刪，且無比較

image.png