2

KD-tree(libkdtree++) を使用して多次元データ セットを格納しました。ここでの要件は、このデータ セットがさまざまな次元で上位 k/範囲クエリをサポートできることです。たとえば、KDTree<3, Point> ツリー: Point[1](y 軸) の値が最も高い上位 100 個のポイントを検索します。

libkdtree++ の実装から、似ているのは「find_within_range」関数ですが、ここでは max(x_dist, max(y_dist, z_dist)) に等しい「マンハッタン距離」に基づいてカウントされます。1 つのディメンションで範囲クエリを使用するにはどうすればよいですか?

4

1 に答える 1

1

コードを見ると、ばかばかしいほど簡単な方法でそれを行うことはできないようです。もし私があなただったら、ライブラリをハックするか、自分の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（y <= Yのポイント）== 100であるYの非常に非効率的な二分探索です。私はライブラリに精通していませんが、大まかな検査で得た最高のものです。

于 2010-07-15T22:55:31.413 に答える