資料結構: 資料的 intrinsic dimensionality (本徵維數) 和/或資料的 sparsity (稀疏度). 本徵維數是指資料所在的流形的維數d<=D, 在引數空間可以是線性或非線性的. 稀疏度指的是資料填充引數空間的程度(這與“稀疏”矩陣中使用的概念不同, 資料矩陣可能沒有零項, 但是從這個意義上來講,它的 structure 仍然是 “稀疏” 的)。Brute force (暴力查詢)時間不受資料結構的影響。Ball tree 和 KD tree 的資料結構對查詢時間影響很大. 一般地, 小維度的 sparser (稀疏) 資料會使查詢更快. 因為 KD 樹的內部表現形式是與引數軸對齊的, 對於任意的結構化資料它通常不會表現的像 ball tree 那樣好.
在機器學習中往往使用的資料集是非常結構化的, 而且非常適合基於樹結構的查詢。
query point（查詢點）所需的近鄰數k。Brute force 查詢時間幾乎不受k值的影響.Ball tree 和 KD tree 的查詢時間會隨著k的增加而變慢. 這是由於兩個影響: 首先, k的值越大在引數空間中搜索的部分就越大. 其次, 使用k>1進行樹的遍歷時, 需要對內部結果進行排序.
當k相比N變大時, 在基於樹的查詢中修剪樹枝的能力是減弱的. 在這種情況下, 暴力查詢會更加有效.
query points（查詢點）數. ball tree 和 KD Tree 都需要一個構建階段. 在許多查詢中分攤時，這種結構的成本可以忽略不計。 如果只執行少量的查詢, 可是構建成本卻佔總成本的很大一部分. 如果僅需查詢很少的點, 暴力方法會比基於樹的方法更好.
最近鄰的快速計算是機器學習中一個活躍的研究領域。最簡單的近鄰搜尋的實現涉及資料集中所有成對點之間距離的暴力計算： 對於 D維度中的N個樣本來說, 這個方法的複雜度是 O[DN²]。 對於小資料樣本，高效的暴力近鄰搜尋是非常有競爭力的。 然而，隨著樣本數N的增長，暴力方法很快變得不切實際了。
KD樹
為了解決效率低下的暴力計算方法，已經發明瞭大量的基於樹的資料結構。總的來說， 這些結構試圖透過有效地編碼樣本的 aggregate distance (聚合距離) 資訊來減少所需的距離計算量。 基本思想是，若A點距離B點非常遠，B點距離C點非常近， 可知點與C點很遙遠，不需要明確計算它們的距離。 透過這樣的方式，近鄰搜尋的計算成本可以降低為O[DNlog(N)]或更低。 這是對於暴力搜尋在大樣本數N中表現的顯著改善。
利用這種聚合資訊的早期方法是 KD tree 資料結構（* K-dimensional tree* 的簡寫）, 它將二維 Quad-trees 和三維 Oct-trees推廣到任意數量的維度. KD 樹是一個二叉樹結構，它沿著資料軸遞迴地劃分引數空間，將其劃分為嵌入資料點的巢狀的各向異性區域。 KD 樹的構造非常快：因為只需沿資料軸執行分割槽, 無需計算D-dimensional 距離。 一旦構建完成, 查詢點的最近鄰距離計算複雜度僅為O[log(N)]。 雖然 KD 樹的方法對於低維度 (D<20) 近鄰搜尋非常快, 當D增長到很大時, 效率變低: 這就是所謂的 “維度災難” 的一種體現。
ball樹
為了解決 KD 樹在高維上效率低下的問題, ball 樹 資料結構就被研發出來了. 其中 KD 樹沿卡迪爾軸（即座標軸）分割資料, ball 樹在沿著一系列的 hyper-spheres 來分割資料. 透過這種方法構建的樹要比 KD 樹消耗更多的時間, 但是這種資料結構對於高結構化的資料是非常有效的, 即使在高維度上也是一樣.
ball 樹將資料遞迴地劃分為由質心 C和半徑r定義的節點,使得節點中的每個點位於由r和C
定義的 hyper-sphere 內. 透過使用 triangle inequality（三角不等式） 減少近鄰搜尋的候選點數:|x+y|<=|x|+|y|透過這種設定, 測試點和質心之間的單一距離計算足以確定距節點內所有點的距離的下限和上限. 由於 ball 樹節點的球形幾何, 它在高維度上的效能超出 KD-tree, 儘管實際的效能高度依賴於訓練資料的結構。
最近鄰演算法的選擇
對於給定資料集的最優演算法是一個複雜的選擇, 並且取決於多個因素:
樣本數量 N(i.e. ) 和維度(例如. ).Brute force 查詢時間以 O[DN]增長Ball tree 查詢時間大約以 O[Dlog(N)]增長KD tree 的查詢時間 D的變化是很難精確描述的.對於較小的D(小於20) 的成本大約是O[Dlog(N)], 並且 KD 樹更加有效.對於較大的D成本的增加接近O[DN], 由於樹結構引起的開銷會導致查詢效率比暴力還要低.對於小資料集 (N小於30),log(N)相當於N, 暴力演算法比基於樹的演算法更加有效. 和 透過提供一個 leaf size 引數來解決這個問題:這控制了查詢切換到暴力計算樣本數量. 使得兩種演算法的效率都能接近於對較小的N的暴力計算的效率.
資料結構: 資料的 intrinsic dimensionality (本徵維數) 和/或資料的 sparsity (稀疏度). 本徵維數是指資料所在的流形的維數d<=D, 在引數空間可以是線性或非線性的. 稀疏度指的是資料填充引數空間的程度(這與“稀疏”矩陣中使用的概念不同, 資料矩陣可能沒有零項, 但是從這個意義上來講,它的 structure 仍然是 “稀疏” 的)。Brute force (暴力查詢)時間不受資料結構的影響。Ball tree 和 KD tree 的資料結構對查詢時間影響很大. 一般地, 小維度的 sparser (稀疏) 資料會使查詢更快. 因為 KD 樹的內部表現形式是與引數軸對齊的, 對於任意的結構化資料它通常不會表現的像 ball tree 那樣好.在機器學習中往往使用的資料集是非常結構化的, 而且非常適合基於樹結構的查詢。
query point（查詢點）所需的近鄰數k。Brute force 查詢時間幾乎不受k值的影響.Ball tree 和 KD tree 的查詢時間會隨著k的增加而變慢. 這是由於兩個影響: 首先, k的值越大在引數空間中搜索的部分就越大. 其次, 使用k>1進行樹的遍歷時, 需要對內部結果進行排序.當k相比N變大時, 在基於樹的查詢中修剪樹枝的能力是減弱的. 在這種情況下, 暴力查詢會更加有效.
query points（查詢點）數. ball tree 和 KD Tree 都需要一個構建階段. 在許多查詢中分攤時，這種結構的成本可以忽略不計。 如果只執行少量的查詢, 可是構建成本卻佔總成本的很大一部分. 如果僅需查詢很少的點, 暴力方法會比基於樹的方法更好.