如何使用KDTree在任意維上進行top-k查詢和範圍查詢

Question

我已經使用KD-tree（libkdtree ++）來存儲多維數據集，並且這裏的要求是這個數據集可以支持top-k /範圍查詢不同維度。例如，KDTree < 3，Point> tree：查找具有最高Point [1]（y軸）值的前100個點。

從libkdtree ++的實現中，類似的是「find_within_range」函數，但是它在這裏基於「曼哈頓距離」計數，該距離等於max（x_dist，max（y_dist，z_dist））。我怎麼才能在一個維度上使用範圍查詢？

Answer 1

看着代碼，看起來你不能以一種簡單的方式做到這一點，足夠可笑。如果我是你，我會試圖破解圖書館或寫我自己的kd-tree。我問他們的郵件列表可以肯定的，但它看起來像你可能需要做這樣的事情：

kdtreetype::_Region_ r(point_with_min_y); 
r.set_low_bound(min_x, 0); 
r.set_high_bound(max_x, 0); 
r.set_low_bound(min_z, 2); 
r.set_high_bound(max_z, 2); 
r.set_high_bound((min_y + max_y)/2, 1); 

double search_min = min_y, search_max = max_y; 

// binary search to get 100 points 
int c; 
while (c = tree.count_within_range(r) != 100) { 
    if (c > 100) search_max = (search_min + search_max)/2; 
    else   search_min = (search_min + search_max)/2; 
    r.set_high_bound((search_min + search_max)/2); 
} 

tree.visit_within_range(r, process_min_y_point); 

這是Y上效率極其低下的二進制搜索，在其爲Y <數（分= Y）== 100.我對圖書館並不熟悉，但這是我在粗略檢查中得到的最好結果。