編者的總結(jié)

1. 本文提出的是一個(gè)預(yù)處理的方法，用于在KNN搜索中削減數(shù)據(jù)集規(guī)模，使得構(gòu)建/運(yùn)行其他KNN算法時(shí)內(nèi)存占用變少。
2. 由于預(yù)處理后數(shù)據(jù)集變少了，那么其他算法的壓縮比就可以放寬一些，精度自然而然也就提升起來(lái)了。

編者的思考

1. 本文提的算法的代價(jià)有點(diǎn)過高，作為一個(gè)預(yù)處理算法，有N2的復(fù)雜度，這是比較夸張的。雖然索引算法的構(gòu)建和查詢的內(nèi)存占用少了，但是這個(gè)預(yù)處理占的資源也比較高了。
2. 核心亮點(diǎn)就是挖出了hubness這一度量，但是對(duì)于更為general的benchmark，即數(shù)據(jù)集數(shù)據(jù)分布和查詢集數(shù)據(jù)分布未必一致吻合時(shí)，是什么情況，還有待考究。

1 INTRODUCTION

• 之前的KNN算法都是需要把整個(gè)數(shù)據(jù)集load到內(nèi)存里來(lái)，這對(duì)于大數(shù)據(jù)集是不合適的。
• 無(wú)論是圖的算法，還是樹的算法，都對(duì)于內(nèi)存開銷的優(yōu)化于事無(wú)補(bǔ)。
• 內(nèi)存要想降下來(lái)，兩條路，一個(gè)是向量summarazation的壓縮比高一些，一個(gè)是讓數(shù)據(jù)集小一些。乘積量化走的第一條路，但是精度損失較大。
• 本文走的是后一條路，刪掉不重要的向量，讓數(shù)據(jù)集規(guī)模降下來(lái)（比如到一半左右）。
  • 不重要，主要指的是中心度hubness，后文詳細(xì)講。
  • 其他異常檢測(cè)算法，即刪除異常點(diǎn)降低規(guī)模，本文也有考慮，在實(shí)驗(yàn)部分有比較，效果不如hubness。

3 WHICH VECTORS ARE UNNECESSARY?

什么是不重要的向量呢？如果給定數(shù)據(jù)集和查詢集，那些數(shù)據(jù)集中不屬于任何query的KNN的向量，就是不重要的向量。
本文的方法就是要?jiǎng)h去一些不重要的向量，處理完數(shù)據(jù)集之后，任何ANN搜索算法都可以用于新的小數(shù)據(jù)集。

3.1 Hubness

首先定義中心度(hubness).節(jié)點(diǎn)的中心度，是指該節(jié)點(diǎn)包含在多少其他節(jié)點(diǎn)（數(shù)據(jù)集中）的KNN。形式化定義如下：

image.png

image.png

• 注意，中心度只和數(shù)據(jù)集有關(guān)，而和查詢集無(wú)關(guān)。
• 中心度高的稱hub，中心度低的，也就是標(biāo)題中的anti-hub。
• 中心度通常用于有監(jiān)督學(xué)習(xí)中，在圖像檢索中，hub通常是有誤導(dǎo)性的，因?yàn)樗痪邆浔鎰e性，和太多其它圖像相似了，anti-hub反而是重要的。
• 但是在ANN算法中，hub反而是重要的，因?yàn)閔ub一般是query的KNN。

3.2 Exploratory Experiment with Deep1M

我們把查詢集的KNN的所有向量構(gòu)成一個(gè)集合，數(shù)據(jù)集中另一部分向量構(gòu)成一個(gè)集合，分別來(lái)算中心度分布，得到如下圖：

image.png

• 可以看到，中心度較低的，一般都不是KNN結(jié)果。
• 最關(guān)鍵的是，中心度的計(jì)算，是與查詢無(wú)關(guān)的。

4 PROPOSED METHOD

4.1 Reduction of Anti-Hubs

有上面的發(fā)現(xiàn)，一種最簡(jiǎn)單的想法就是每個(gè)節(jié)點(diǎn)都算一下中心度，取前T個(gè)最大的保留就好了。

• 但是算中心度代價(jià)太高，向量?jī)蓛捎?jì)算距離就是的復(fù)雜度。
• 另一個(gè)問題就是，如果query是和anti-hub離得比較近的話，那么召回就丟失了。但是我們的假設(shè)是：數(shù)據(jù)集的分布和查詢集的分布是類似的。那么查詢也將趨向于靠近hub，數(shù)據(jù)集削減對(duì)整體的影響就沒有那么大。

4.2 Approximation

上述方法復(fù)雜度太高，至少應(yīng)該把距離計(jì)算的復(fù)雜度降下來(lái)。
作者的方法也非常簡(jiǎn)單：分治。
數(shù)據(jù)集首先做K-means，在每個(gè)聚類里面分別運(yùn)行4.1的方法，再合并起來(lái)。

• 這樣下來(lái)，距離計(jì)算的復(fù)雜度就變成了，C是聚類的個(gè)數(shù)。
• 但是這樣做的代價(jià)是肯定不如之前算法的精確度要高。
• 對(duì)于300+GB的Deep1B數(shù)據(jù)集，文中取C=1000,96個(gè)線程，跑了70個(gè)小時(shí)，其中K-means花了不足40min。用GPU之后，可縮減到5個(gè)小時(shí)。

5 EXPERIMENTS

4個(gè)GPU， 3.6 GHz Intel Xeon CPU (24 cores, 96 threads) and 192 GiB內(nèi)存。
python多線程寫的。 k設(shè)為16.

image.png

5.5 Comparison with Other??ReductionMethods

• RR是隨機(jī)刪數(shù)據(jù)，KNNOD是基于KNN的異常檢測(cè)算法刪數(shù)據(jù)，F(xiàn)ABOD是基于角度的異常檢測(cè)算法刪數(shù)據(jù)。

• 刪完數(shù)據(jù)之后做精確查詢，召回率如圖，本文的最好。

  
  
  image.png

5.6 Comparison with Other Reduction Methods

• 在保證內(nèi)存占用（壓縮效率）不變的情況下，將本文的方法和其它向量壓縮方法組合使用，可以獲得更高的召回。

  
  
  image.png

5.8 Validation of Approximation Process

• 這個(gè)實(shí)驗(yàn)驗(yàn)證K-means的近似不會(huì)損失太多。

• 可以看到，提高C，即聚類個(gè)數(shù)，對(duì)于最終召回沒有太大影響。

  
  
  image.png