1

このR*ツリーの実装を読んでいたところ、紙で定義されている方法とは異なる方法でオーバーラップを計算していることに気付きました。

この論文では、オーバーラップは次のように定義されています。

与えられたノード/rectkについて、 kとkの各兄弟（ kを含まない）の間の交点の面積の合計を計算します。

オーバーラップ拡大は、この値のデルタであり、アイテムrがkに追加された場合のノードkのオーバーラップは何ですか。

このようなもの：

childOverlapEnlargement(Node child, item r)
{
    childEnlarged = child.union(r);
    sum = 0;
    for(each sibling s of child which isn't node)
    {
        sum += area(childEnlarged.intersect(s)) - area(child.intersect(s));
    }
    return sum;
}

他の実装では、挿入されているアイテムと特定のノードの交差領域で並べ替えます。このようなもの：

childOverlapEnlargement(Node node, item r)
{
    return area(node.intersect(r));
}

明らかに、それらの実装は、論文の定義よりも計算量が少なくて済みます。ただし、2つの計算が等しくなければならない理由は明らかではありません。

だから私の質問は：

  1. 2つの計算は常に同じサブツリーが選択されることになりますか？なんで？
  2. 異なるサブツリーが選択される結果になる場合、結果は論文の定義と同じくらい良いですか、それとも近いですか？それとも誤った選択でしたか？

編集：それらの実装を読み直して、2人の兄弟の交差点を比較しているのではなく、それぞれの潜在的な葉と挿入されているアイテムの交差点を比較していることに気付きました。不思議なことに、彼らは挿入されているアイテムと最も重ならない兄弟を選んでいます。挿入するアイテムと最も重なるノードに挿入しませんか？

4

1 に答える 1

1

おそらく、あなたが見ている実装にはバグがあるか、正しくありません。誰も完璧ではありません。

R *ツリーは、それ自体がオーバーラップするのではなく、オーバーラップの拡大を最小化しようとすることに注意してください。

一部の重複は避けられない可能性があります。すでにオーバーラップがある場合、追加の長方形を挿入するときにこれが作成解除されることは期待できません。ただし、少なくともオーバーラップの量を増やさないようにすることはできます。

パフォーマンスの考慮事項については、交差する長方形を実際に計算する必要があるかどうかを確認してください。area(intersection())関数を実行するために計算する代わりにしようとしますintersectionSize()。これは違いを生みます。たとえば、他の次元を見なくても、交差点のサイズを0にするとすぐに指定できますA.maxX = 1。B.minX = 2

必要になる可能性のあるすべての交差点などを熱心に事前計算することは避けてください。代わりに、実際に必要なものだけを計算してください。コードのプロファイルを作成し、重要なコードパスを最適化できるかどうかを確認します。そこには通常、ぶら下がっている果物がいくつかあります。

于 2013-01-16T07:35:29.617 に答える