我用过KD-tree(libkdtree++)来存储一个多维数据集,这里的要求是这个数据集可以支持不同维度的top-k/range查询。例如,KDTree<3, Point> 树:找到具有最高 Point[1](y 轴)值的前 100 个点。
从libkdtree++的实现来看,类似的是“find_within_range”函数,只不过是根据“曼哈顿距离”计算的,这里等于max(x_dist, max(y_dist, z_dist))。如何仅在一维上使用范围查询?
最佳答案
看看代码,看起来你不能以一种直截了当的方式做到这一点,这太荒谬了。如果我是你,我会很想破解图书馆或编写我自己的 kd 树。我会在他们的邮件列表上询问以确保确定,但看起来你可能必须做这样的事情:
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);
对于 count(points with y <= Y) == 100 处的 Y,这是一个非常低效的二进制搜索。我不熟悉该库,但这是我粗略检查时得到的最好结果。
关于c++ - 如何使用KDTree进行任意维度的top-k查询和范围查询,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3260601/