algorithm - 二次分割と線形分割の違い

Question

r ツリーがどのように機能するかを理解しようとしていますが、分割には 2 次と線形の 2 種類があることがわかりました。

線形と二次の実際の違いは何ですか? どちらの場合、一方が他方よりも優先されますか?

Answer 1

さらに多くのバリアントがあります: 徹底的な検索、Greenes 分割、Ang Tan 分割、R* ツリー分割。

それらはすべて、許容可能な時間内に適切な分割を見つけるためのヒューリスティックです。

私の実験では、より多くの長方形のページが生成されるため、R* ツリー分割が最もうまく機能します。Ang-Tan は、「線形」である一方で、実際にはほとんどのクエリにとって厄介なスライスを生成します。多くの場合、構築/挿入時のコストはそれほど重要ではありませんが、クエリは重要です。

Answer 2

どちらも小さな領域の分割を見つけるためのヒューリスティックです。

二次では、できるだけ多くの空きスペースを作成する 2 つのオブジェクトを選択します。線形では、最も離れた 2 つのオブジェクトを選択します。

Quadratic は、分割の品質を少し向上させます。ただし、多くの実用的な目的では、線形は二次と同じくらい簡単で高速で優れています。

Answer 3

元の R ツリー ペーパーでは、セクション 3.5.2 と 3.5.3 で PickSeeds と LinearPickSeeds の違いについて説明し、セクション 4 のグラフは 2 つのアルゴリズムのパフォーマンスの違いを示しています。図 4.2 では、Y 軸に指数スケールを使用していることに注意してください。

http://www.cs.bgu.ac.il/~atdb082/wiki.files/paper6.pdf

個人的には、R ツリーの「チャーン」が多く、メモリ使用量が重要でない場合には LinearPickSeed を使用し、R ツリーが比較的静的であるか、メモリが限られている環境にある場合には QuadraticPickSeed を使用します。しかし、これは単なる経験則です。それを裏付けるベンチマークはありません。