查找大集合中的nearset鄰居

Question

我在多維空間中有大量的點。我想找到幾個鄰居（在附近）任何給定的點（要求是爲了避免掃描所有點）。

我想知道如果我的解決辦法是適當的：

預處理：

1. 定義設置的ortogonal軸系
2. 使每個點的投影每個軸上
3. 每個投影都與從軸（鍵）的起點到點（值）的標識符的距離相關聯。 指數預測 - 把所有的人都到有序set（如樹集）

dist = distance of projection to the start point of axis 
point_num = number of point 
sorted_set.put(dist, point_num) 

找到任何給定的點的鄰居：

1. 查找其投射在每個軸上
2. 使用idexes - 在每個exis上查找最近投影數
3. 查找實際的鄰居 - 相交所有的導致

dx = radius of neighborhood (some constant) 

dist_1 = distance of projection of given point to start point of axis_1 
list_1 = sorted_set_1.get_sub_set(dist_1 - dx, dist_1 + dx) 

dist_2 = distance of projection of given point to start point of axis_2 
list_2 = sorted_set_2.get_sub_set(dist_2 - dx, dist_2 + dx) 

return intersection_of(list_1, list_2) 

下面是一個簡單的例子：

相交[2, 4, 1]和[4, 5]產生回答[4]

請點我，如果我在我的算法來實現任何錯誤

感謝

Answer 1

你還沒有給我們關於如何建立你的實際鄰居設置指令，在這種情況下[2, 4, 1]和[4, 5]。你爲什麼選擇一個索引中的3個元素和另一個索引中的2個？

你還聲明你想找幾個鄰居。有多少是應該作爲您的功能的輸入？在這個例子中，你只能找到一個，算法決定你想要多少？

在所有點位於某個軸上的某一行上的情況下會發生什麼情況？那麼一套肯定會包含所有元素。