Как использовать KDTree для выполнения запросов top-k и диапазона в произвольных измерениях - PullRequest
Новая
       19

Как использовать KDTree для выполнения запросов top-k и диапазона в произвольных измерениях

2 голосов
/ 16 июля 2010

Я использовал KD-дерево (libkdtree ++) для хранения многомерного набора данных, и требования здесь - этот набор данных может поддерживать запросы top-k / range в различных измерениях.Например, дерево KDTree <3, Point>: для поиска 100 верхних точек, которые имеют самые высокие значения Point [1] (ось y).

Из реализации libkdtree ++ аналогично функции "find_within_range", однако они рассчитываются на основе "расстояния Манхэттена", которое здесь равно max (x_dist, max (y_dist, z_dist)).Как я могу просто использовать запрос диапазона в одном измерении?

1 Ответ

1 голос
/ 16 июля 2010

Глядя на код, кажется, что вы не можете сделать это простым способом, достаточно смешно.Если бы я был тобой, я бы хотел либо взломать библиотеку, либо написать свое собственное 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);

Это ужасно неэффективный двоичный поиск для Y, при котором количествоy <= Y) == 100. Я не знаком с библиотекой, но это лучшее, что я получил при беглом осмотре. </p>

...