空間インデックスに関する良い本/記事

Question

私は空間インデックスに関する良い文献に興味があります。どれが使用されているか、スピード、スペース要件、それらを使用するときの空間クエリのパフォーマンスなどの中で、それらの間の比較。

Answer 1

私は空間インデックス作成のために一種の自家製QuadTreeを使用していました（ "quadtree "）。通常の種類の空間データ（私はストリートマップデータを扱います）では、作成するのが速く、クエリーを高速化しますが、クエリー中にリーフノードをスキャンする回数が多すぎます。具体的には、合理的なノードサイズ（50-100）では、私のクアッドツリーはポイントクエリーで約300の結果を生む傾向がありました。つまり、3-6リーフノードが適用されます（非常にラフな野球場で、結果は非常に変動します）。

今日、私好ましいデータ構造はR *ツリーである。私は非常に良い結果を得た実装を自分で書いてテストしました。 R *ツリーを構築するための私のコードは私のQuadTreeコードに比べて非常に遅いですが、リーフノード上のバウンディングボックスは非常にうまく構成されています。問合せ空間の少なくとも半分が唯一のリーフ・ノードによって応答されます（つまり、ランダム・ポイント問合せを実行する場合、単一のリーフ・ノードのみが返される可能性が高い）。その90％の領域が2つ以下のノード。だから、80要素のノードサイズでは、私は通常、平均が160に近づく（いくつかのクエリが3-5ノードを返すので）、ポイントクエリから80または160の結果を得るだろう。これは地図の密集した都市部でさえ当てはまります。

私は自分のR *ツリーとその中のグラフィカルオブジェクトのビジュアライザーを書いたので、これを知っています。大きなデータセット（60万の道路セグメント）でテストしました。ポイントデータ（およびバウンディングボックスがほとんど重ならない他のデータ）でさらに優れたパフォーマンスを発揮します。 R *ツリーを実装した場合、結果を視覚化することを強くお勧めします。なぜなら、私が執筆したときに、ツリーの効率を低下させる複数のバグがあったからです（正確性に影響することなく）。より良い結果を得る。小さなデータセットにはない問題が明らかになるので、大規模なデータセットでテストしてください。テストのためにツリーのファンアウト（ノードサイズ）を減らし、ツリーがいくつかのレベルに深いときにツリーがどれほどうまく動作するかを確認するのに役立ちます。

雇用主の許可が必要であることを除いて、ソースコードを教えていただきたいと思います。それはどういうことか分かります。私の実装では強制再挿入をサポートしていますが、私のPickSplitと の挿入ペナルティは調整されています。

オリジナルペーパーThe R* tree: An Efficient and Robust Access Method for Points and Rectanglesは何らかの理由でドットが欠落しています（「i」にはピリオドやドットはありません）。また、その用語は少し奇妙です。彼らが「マージン」と言うとき、彼らが意味するのは「境界」です。

変更可能なデータ構造が必要な場合は、R *ツリーが適しています。ツリーを最初に作成した後にツリーを変更する必要がない場合は、bulk loading algorithmsを検討してください。バルクロード後にツリーを少々修正する必要がある場合は、通常のRツリーアルゴリズムで十分です。 R *ツリーとRツリーのデータは構造的に同一であることに注意してください。挿入アルゴリズム（と削除の可能性はありますか？忘れてしまいます）だけが異なります。 R-treeは1984年の元のデータ構造です。 R-tree paperへのリンクがあります。

kd-treeは効率的で、実装するのが難しくはありませんが、ポイントデータにしか使用できません。ところで

、私はリーフノードに焦点を当てる理由はそんなに私は、ディスクベースの空間索引に対処する必要がある

1. ということです。一般的に、すべての内部ノードはインデックスサイズのごくわずかな部分であるため、メモリにキャッシュできます。したがって、それらをスキャンするのに要する時間は、キャッシュされていないリーフノードに必要な時間と比較して小さい。
2. 空間インデックスに要素のバウンディングボックスを格納しないことで、多くの領域を節約できます。つまり、クエリに応答するために各要素の元のジオメトリを実際にテストする必要があります。したがって、タッチされたリーフノードの数を最小限に抑えることがさらに重要です。

Answer 2

象限ベースの高速検索のアルゴリズムを開発し、数年前にddj.comに公開しました。多分それはあなたのための興味深いです：最寄りのライン http://drdobbs.com/windows/198900559

については

加速検索