主要算法

　　Kd-Tree

　　K-dimension tree，二叉樹結構，對數據點在k維空間（如二維 (x，y)，三維(x，y，z)，k維(x，y，z..)）中劃分。

　　構建過程

　　確定split域的值(輪詢 or 最大方差)

　　確定Node-data的域值（中位數 or 平均值）

　　確定左子空間和右子空間

　　遞歸構造左右子空間

　　查詢過程

　　進行二叉搜索，找到葉子結點

　　回溯搜索路徑，進入其他候選節點的子空間查詢距離更近的點

　　重復步驟2，直到搜索路徑為空

　　性能

　　理想情況下的復雜度是O(K log(N)) 最壞的情況下（當查詢點的鄰域與分割超平面兩側的空間都產生交集時，回溯的次數大大增加）的復雜度為維度比較大時，直接利用K-d樹快速檢索（維數超過20）的性能急劇下降，幾乎接近線性掃描。

　　改進算法

　　Best-Bin-First：通過設置優先級隊列（將“查詢路徑”上的結點進行排序，如按各自分割超平面與查詢點的距離排序）和運行超時限定（限定搜索過的葉子節點樹）來獲取近似的最近鄰，有效地減少回溯的次數。采用了BBF查詢機制后Kd樹便可以有效的擴展到高維數據集上 。

　　Randomized Kd tree：通過構建多個不同方向上的 Kd tree，在各個 Kd tree上并行搜索部分數量的節點來提升搜索性能（主要解決BBF算法隨著Max-search nodes增長，收益減小的問題）

　　Hierarchical k-means trees

　　類似k-means tree，通過聚類的方法來建立一個二叉樹來使得每個點查找時間復雜度是O(log n) 。

　　構建過程 ：

　　隨機選擇兩個點，執行k為2的聚類，用垂直于這兩個聚類中心的超平面將數據集劃分

　　在劃分的子空間內進行遞歸迭代繼續劃分，直到每個子空間最多只剩下K個數據節點

　　最終形成一個二叉樹結構。葉子節點記錄原始數據節點，中間節點記錄分割超平面的信息

　　搜索過程

　　從根節點開始比較，找到葉子節點，同時將路徑上的節點記錄到優先級隊列中

　　執行回溯，從優先級隊列中選取節點重新執行查找

　　每次查找都將路徑中未遍歷的節點記錄到優先級隊列中

　　當遍歷節點的數目達到指定閾值時終止搜索

　　性能

　　搜索性能不是特別穩定，在某些數據集上表現很好，在有些數據集上則有些差

　　構建樹的時間比較長，可以通過設置kmeans的迭代次數來優化

　　LSH

　　Locality-Sensitive Hashing 高維空間的兩點若距離很近，他們哈希值有很大概率是一樣的；若兩點之間的距離較遠，他們哈希值相同的概率會很小 。

　　一般會根據具體的需求來選擇滿足條件的hash函數，(d1,d2,p1,p2)-sensitive 滿足下面兩個條件（D為空間距離度量,Pr表示概率）：

　　若空間中兩點p和q之間的距離D(p,q)p1

　　若空間中兩點p和q之間的距離D(p,q)>d2，則Pr(h(p)=h(q))<p2

　　離線構建索引

　　選擇滿足(