2

この論文に基づいて R* ツリーの実装に取り​​組んでいます。分割軸の選択アルゴリズムについていくつか質問があります。

R* ツリーは、適切な分割を見つけるために followmg メソッドを使用します。各軸に沿って、エントリは最初に低い値で並べ替えられ、次に長方形の高い値で並べ替えられます。

長方形の下限値/上限値とはどういう意味ですか?

各分布について、良さの値が決定されます。これらの良さの値に応じて、エントリの最終的な分布が決定されます。3 つの異なる Goodness 値と、それらをさまざまな組み合わせで使用するさまざまなアプローチが実験的にテストされています。

(I) 面積値 面積[bb(第1グループ)] + 面積[bb(第2グループ)]

(II) margin-value margin[bb(第 1 グループ)] + margin[bb(第 2 グループ)]

(III) 重複値領域 [bb(第 1 グループ) + bb(第 2 グループ)]

ここで、bb は一連の長方形のバウンディング ボックスを示します。

とはどういう意味margin-valueですか? この値を計算するにはどうすればよいですか?

4

2 に答える 2

5

私の知る限り、「長方形の下限/上限値」は、問題の軸に沿った長方形の最小値と最大値です。

リンク先の記事のp323によると、「ここでのマージンは、長方形のエッジの長さの合計です」。

于 2013-01-11T22:56:14.110 に答える
2

長方形は通常、各次元の最小値と最大値のペアで表されます。したがって、「上限」と「下限」の値は最小値と最大値です。

マージンは周囲です。その理由は、多くの状況で、正方形が長方形の好ましいタイプであるためです。たとえば、ユークリッド (またはマンハッタン、ほぼすべての Lp ノルム) 最近傍検索を行う場合。その理由は、それらがある程度「偏りがない」からです。

Ang et Tan による「線形」分割などの他の分割戦略では、これが無視され、非常に長いスライスが生成される傾向があります。ウィキペディアには、この例があります。

https://en.wikipedia.org/wiki/File:Zipcodes-Germany-AngTanSplit.svg

これらは、R* ツリーが回避しようとする種類の分割です。ほとんどのクエリはこれらのスライスの多くと交差するため、得られるものはほとんどありません。

R* ツリーは、多くのヒューリスティックとタイ ブレーカーを使用することに注意してください。さらに、2 段階の決定を行います。まず、分割に使用する軸のみを選択します。軸が決定されると、実際には別のロジックを使用して、この軸に沿った分割が選択されます。

于 2013-01-12T10:19:08.637 に答える