kd-tree BBF算法時間複雜度

Question

我有2000個點，5000個維度，我想得到最近的鄰居。

現在我有一些問題，有人可以給出答案。

1. 人們說，它在高維度上效果很好。時間複雜度是多少？

2. @param max_nn_chks搜索我讀的算法後檢查該樹的許多條目

   切斷後，我不知道我會得到錯誤的答案時，我設置max_nn_chks太低。如果是的話，那就告訴我如何設置這個參數，否則給個理由，謝謝。

3. kdtree是我的數據獲取最近鄰居的最佳數據結構嗎？

Answer 1

1. 的時間複雜度是基本相同的限制KD樹搜索加一些小的時間內保持優先級隊列。受限的KD-Tree搜索算法需要遍歷樹的全部深度（點數的log2）乘以限制（允許訪問的葉節點/點的最大數量）。

2. 是的，如果限制太低，你會得到一個錯誤的答案。您只能測量發現的真正NN的分數與搜索到的葉節點的數量。從這裏，你可以確定你的最佳值。

3. 通常隨機化的kd-tree森林和分級k-means樹表現最好。 FLANN提供了一種確定使用哪種算法（k-均值vs隨機kd-樹林）併爲您設置最佳參數的方法。

數據的結構也有很大的影響。例如，如果您知道有多個點集合在一起，則可以將它們分組在一個樹的單個節點中（例如，用它們的質心表示它們），並加快搜索速度。

其他技術如視覺詞，PCA或隨機投影可用於數據。這是一個相當活躍的研究領域。