典型場景：圖像檢索崇呵。高維檢索域慷。
本質： 很多稠密向量，要迅速找到某個點的臨近點抵窒，并認為這是相似度最高的點叠骑。
原始數據的表達形式為宙枷，N維連續(xù)值的向量。如果針對一個query卓囚，進行暴力搜索诅病，需要計算N次，并進行排序讨阻。而幾乎所有的ANN方法都是對全空間的劃分篡殷，可以迅速找到子空間贴唇，并與子空間內的數據進行計算。方法分為三大類：基于樹的方法飞袋、哈希方法戳气、矢量量化方法。
基于樹的方法采用樹這種數據結構的方法來表達對全空間的劃分巧鸭，其中又以KD樹最為經典瓶您，下面分別對KD樹和Annoy進行簡單介紹。
1.1 KD樹
構建樹的過程纲仍，就是選擇分裂節(jié)點呀袱，并分裂的過程。
節(jié)點選擇：方差最大的那個維度郑叠。方差的大小可以反映數據的波動性。方差大表示數據波動性越大乡革，選擇方差最大的開始劃分空間寇僧，可以使得所需的劃分面數目最小，反映到樹數據結構上沸版，可以使得我們構建的KD樹的樹深度盡可能的小嘁傀。(用方差進行選擇，也就意味著特征值都在相同取值范圍內)
分裂點：视粮？
停止條件：细办？
在空間維度比較低的時候，KD樹是比較高效的蕾殴，當空間維度較高時笑撞，可以采用下面的哈希方法或者矢量量化方法。
1.2 Annoy?
Annoy的核心是不斷用選取的兩個質心的法平面對空間進行分割区宇，最終將每一個區(qū)分的子空間里面的樣本數據限制在K以內娃殖。對于待插入的樣本xi，從根節(jié)點依次使用法向量跟xi做內積運算议谷，從而判斷使用法平面的哪一邊（左子樹or右子樹）炉爆。對于查詢向量qi，采用同樣的方式（在樹結構上體現為從根節(jié)點向葉子節(jié)點遞歸遍歷），即可定位到跟qi在同一個子空間或者鄰近的子空間的樣本芬首，這些樣本即為qi近鄰赴捞。返回的結果無序，因為Annoy樹不保存特征郁稍。保存原始的特征的壞處是造成占用內存過大赦政，索引文件過大。
為了提高查詢的召回耀怜，Annoy采用建立多棵樹的方式恢着。
2.?哈希方法（局部敏感哈希）
局部敏感：相近的樣本點對比相遠的樣本點對更容易發(fā)生碰撞。
加速查找：首先找到查詢樣本落入在哪個cell(即所謂的桶)中财破，只需要在當前的cell中遍歷比較掰派，而不用在所有的數據集中進行遍歷。
多表哈希：對于單表哈希左痢，當我們的哈希函數數目K取得太大靡羡，查詢樣本與其對應的最近鄰落入同一個桶中的可能性會變得很微弱，針對這個問題俊性，我們可以重復這個過程L次略步，從而增加最近鄰的召回率。這個重復L次的過程定页，可以轉化為構建L個哈希表趟薄，這樣在給定查詢樣本時，我們可以找到L個哈希桶（每個表找到一個哈希桶）典徊，然后我們在這L個哈希表中進行遍歷竟趾。這個過程相當于構建了K*L個哈希函數(注意是“相當”，不要做“等價”理解)宫峦。
多表哈希中哈希函數數目K和哈希表數目L如何選炔砻薄：哈希函數數目K過小，會導致每一個哈希桶中容納了太多的數據點导绷，從而增加了查詢響應的時間犀勒；而當K過大時，會使得落入每個哈希桶中的數據點變小妥曲，而為了增加召回率贾费，我們需要增加L以便構建更多的哈希表，但是哈希表數目的增加會導致更多的內存消耗檐盟，并且也使得我們需要計算更多的哈希函數褂萧，同樣會增加查詢相應時間。這聽起來非常的不妙葵萎，但是在K過大或過小之間仍然可以找到一個比較合理的折中位置导犹。通過選取合理的K和L唱凯，我們可以獲得比線性掃描極大的性能提升。
Multiprobe：對于構建的L個哈希表谎痢，我們在每一個哈希表中找到查詢樣本落入的哈希桶磕昼，然后再在這個哈希桶中做遍歷，而Multiprobe指的是我們不止在查詢樣本所在的哈希桶中遍歷节猿，還會找到其他的一些哈希桶票从，然后這些找到的T個哈希桶中進行遍歷。這些其他哈希桶的選取準則是：跟查詢樣本所在的哈希桶鄰近的哈希桶滨嘱，“鄰近”指的是漢明距離度量下的鄰近峰鄙。主要是為了提高查找準確率而引入的一種策略。通常太雨，如果不使用Multiprobe先馆，我們需要的哈希表數目L在100到1000之間，在處理大數據集的時候躺彬，其空間的消耗會非常的高，幸運地是梅惯，因為有了上面的Multiprobe的策略宪拥，LSH在任意一個哈希表中查找到最近鄰的概率變得更高，從而使得我們能到減少哈希表的構建數目铣减。
綜上她君，對于LSH，涉及到的主要的參數有三個：
K葫哗，每一個哈希表的哈希函數（空間劃分）數目
L缔刹，哈希表（每一個哈希表有K個哈希函數）的數目
T，近鄰哈希桶的數目劣针，即the number of probes
這三個設置參數可以按照如下順序進行：首先校镐，根據可使用的內存大小選取L，然后在K和T之間做出折中：哈希函數數目K越大捺典，相應地鸟廓，近鄰哈希桶的數目的數目T也應該設置得比較大，反之K越小襟己，L也可以相應的減小引谜。獲取K和L最優(yōu)值的方式可以按照如下方式進行：對于每個固定的K，如果在查詢樣本集上獲得了我們想要的精度擎浴，則此時T的值即為合理的值员咽。在對T進行調參的時候，我們不需要重新構建哈希表贮预，甚至我們還可以采用二分搜索的方式來加快T參數的選取過程贝室。
3.1 矢量量化方法
其具體定義為：將一個向量空間中的點用其中的一個有限子集來進行編碼的過程契讲。在矢量量化編碼中，關鍵是碼本的建立和碼字搜索算法档玻。比如常見的聚類算法怀泊，就是一種矢量量化方法。
PQ乘積量化：
1）特征維度為128維误趴，分為4個子段霹琼，4個子空間，每個子空間32維凉当；
2）各個子段（子空間）枣申，用更少的特征，進行聚類看杭。每一個子空間都能得到一個碼本忠藤。則每個樣本的每個子段，可以映射到一個ID楼雹，這個ID對應的是（子空間的聚類中心）模孩。則 訓練樣本僅使用的很短的一個編碼得以表示，從而達到量化的目的贮缅。對于待編碼的樣本榨咐，將它進行相同的切分，然后在各個子空間里逐一找到距離它們最近的類中心谴供，要遍歷的是每個類中心块茁，然后用類中心的id來表示它們，即完成了待編碼樣本的編碼桂肌。
3）查詢樣本與dataset（候選集）中的樣本距離的計算数焊。
有兩種距離計算方式，一種是對稱距離崎场，另外一種是非對稱距離佩耳。非對稱距離的損失小(也就是更接近真實距離)，實際中也經常采用這種距離計算方式谭跨。
1) 查詢向量來到時蚕愤，按訓練樣本生成碼本的過程，將其同樣分成相同的子段饺蚊，然后在每個子空間中萍诱，計算子段到該子空間中所有聚類中心得距離，如圖中所示污呼，可以得到4*256個距離裕坊，把這些算好的距離稱作距離池。
在計算庫中某個樣本到查詢向量的距離時燕酷，比如編碼為(124, 56, 132, 222)這個樣本到查詢向量的距離時籍凝，我們分別到距離池中取各個子段對應的距離即可周瞎，比如編碼為124這個子段，在第1個算出的256個距離里面把編號為124的那個距離取出來就可饵蒂，所有子段對應的距離取出來后声诸，將這些子段的距離求和相加，即得到該樣本到查詢樣本間的非對稱距離退盯。所有距離算好后彼乌，排序后即得到我們最終想要的結果。
從上面這個過程可以很清楚地看出PQ乘積量化能夠加速索引的原理：即將全樣本的距離計算渊迁，轉化為到子空間類中心的距離計算慰照。比如上面所舉的例子，原本brute-force search的方式計算距離的次數隨樣本數目N成線性增長琉朽，但是經過PQ編碼后毒租，對于耗時的距離計算，只要計算4*256次箱叁，幾乎可以忽略此時間的消耗墅垮。另外，從上圖也可以看出耕漱，對特征進行編碼后算色，可以用一個相對比較短的編碼來表示樣本，自然對于內存的消耗要大大小于brute-force search的方式孤个。
在某些特殊的場合，我們總是希望獲得精確的距離沛简，而不是近似的距離齐鲤，并且我們總是喜歡獲取向量間的余弦相似度（余弦相似度距離范圍在[-1,1]之間，便于設置固定的閾值）椒楣，針對這種場景给郊，可以針對PQ乘積量化得到的前top@K做一個brute-force search的排序。
3.2 倒排乘積量化
倒排PQ乘積量化(IVFPQ)是PQ乘積量化的更進一步加速版捧灰。其加速的本質逃不開最前面強調的是加速原理：brute-force搜索的方式是在全空間進行搜索淆九，為了加快查找的速度，幾乎所有的ANN方法都是通過對全空間分割毛俏，將其分割成很多小的子空間炭庙，在搜索的時候，通過某種方式煌寇，快速鎖定在某一（幾）子空間焕蹄，然后在該（幾個）子空間里做遍歷。在上一小節(jié)可以看出阀溶，PQ乘積量化計算距離的時候腻脏，距離雖然已經預先算好了鸦泳，但是對于每個樣本到查詢樣本的距離，還是得老老實實挨個去求和相加計算距離永品。但是做鹰，實際上我們感興趣的是那些跟查詢樣本相近的樣本（小白菜稱這樣的區(qū)域為感興趣區(qū)域），也就是說老老實實挨個相加其實做了很多的無用功鼎姐，如果能夠通過某種手段快速將全局遍歷鎖定為感興趣區(qū)域钾麸，則可以舍去不必要的全局計算以及排序。倒排PQ乘積量化的”倒排“症见，正是這樣一種思想的體現喂走，在具體實施手段上，采用的是通過聚類的方式實現感興趣區(qū)域的快速定位谋作，在倒排PQ乘積量化中芋肠，聚類可以說應用得淋漓盡致。
總結下來：
樹方法：用一顆或多顆樹遵蚜，把樣本劃分到小區(qū)間帖池。如果數據量大，特征多吭净，則樹就深睡汹。要從根節(jié)點走下去，效率就低寂殉。
Hash 方法：將不同樣本劃分在不同的桶中囚巴，桶相同，則為候選相似樣本友扰。
PQ方法：距離預先算好彤叉，編碼長度較短。
參考：https://yongyuan.name/blog/ann-search.html
