algorithm - Rtrees-アルゴリズムの基本

Question

私はRTreeアルゴリズムの基本を理解しようとしています。また、RTreeアルゴリズムが1km以内のすべてのレストランの検索をどのように実行するかを理解しようとしています。データベース内の長方形にすべてのオブジェクトを格納し、（おそらく）現在の位置に基づいてクエリ長方形を作成し、それと重なるすべての長方形を見つけます。次に、結果をスキャンして、関心のあるもの、つまりレストランであるオブジェクトのみを見つけますか？

Answer 1

はい、これは基本的に R ツリーでの範囲クエリのしくみです: 四角形がクエリ領域と重なる場合は、それを拡張します (コンテンツ、四角形、または点を見てください)。それ以外の場合は、無視してください。オーバーラップ テストは、四角形から四角形への単純なものであり、球形クエリの場合は、球の中心から四角形までの最小距離 ("minDist") を計算する必要があります。

k 最近隣クエリはもう少しトリッキーです。ここでは優先キューが必要です。次の長方形「minDist」よりも近い k 個のオブジェクトが見つかるまで、常に最良の候補を (「minDist」で) 拡張します。

「is a restaurant」プロパティを実際にインデックス化することはできないため、レストランのみを含む r ツリーを構築するか、レストラン プロパティで結果をフィルタリングする必要があります。(これは、SQLite などで行われる方法でもあります。空間部分は R ツリーでインデックス付けされますが、レストラン プロパティは、結合またはビットマップ インデックスを介して取得されます)

R ツリーの難しい部分はクエリではなく、それを構築する方法です。ポイント データ (STR) を大量にロードするための非常に単純で優れた方法がありますが、オンライン データベースの場合はややトリッキーな方法が必要です。私の経験では、R* ツリーは従来の R ツリーよりも大幅に優れています。R* ツリーで使用される再挿入は、実際の DBMS で実装するのが特に難しいです。興味深いトレードオフは、R* からの挿入と分割のみを使用し、再挿入は使用しないことです。とにかく、クエリ側では、R と R* の間に違いはありません。

kd-trees: これらは r-trees に関連していますが、いくつかの重要な違いがあります。まず第一に、それらはディスクストレージ用に設計されておらず、メモリ内操作のみを対象としています。第二に、それらは更新されることを意図していません (バランスの取れたツリーではありません) が、変更がある場合は、パフォーマンスを良好に保つために時々再構築する必要があります。そのため、場合によっては非常にうまく機能します (そして、実装が非常に簡単です) が、大きなデータとディスク上に到達すると、はるかに苦痛になります。さらに、それらは異なる読み込み戦略を許可しません。