問題タブ [spatial-index]

現在、Lat / Long float列を含むテーブルと、これら2つの列のインデックスと取得する必要のある別の列があるサイトがあります。

私は常にこのテーブルをクエリして、特定のポイントから半径内にある行を取得しています（実際には速度のために正方形を取得しています）が、すでにインデックスが作成されているフィールドのみが必要なので、このインデックスは実際にカバーしています、および実行プランには2つのステップしかありません。

現在、SQL 2008の空間機能を利用しようとしています。地理列を作成し、それを埋め、空間インデックスを作成しました。

また、実行プランに100万ステップがあり、時間の74％がクラスター化インデックスシークに費やされ、空間インデックスで見つかった行を実際のテーブルに結合して残りを取得することを除いて、すべて正常に機能します。データの...
（空間インデックスシークは実行プランコストの1％を占めます）

したがって、明らかに、Spatialインデックスを適切に使用し、Lat / Longの「通常の」インデックスを使用して、以前よりもはるかに高速に必要なレコードを検索していますが、メインテーブルへの結合はKILLING meであり、Spatialクエリは7倍かかります。私の古いものと同じくらい。

空間インデックスに列を追加して、それがカバーされ、以前と同じように1つのステップで実行できるようにする方法はありますか？
この状況を改善するために私ができる他のことはありますか？

更新：「通常の」インデックスは、INCLUDEキーワードを使用して他の列を「含める」ことができることがわかりました（これは知らなかったので、以前はインデックス自体に列を含めるだけでした）ここ
のドキュメントによると、その句はそうではありません空間インデックスのオプション...何かアイデアはありますか？

ありがとう！
ダニエル

x、yペアのリストがあります。すべてのペアは、2D空間上の点を表します。このリストから特定のポイントxq、yqに最も近いポイントを見つけたいと思います。この問題に最適なパフォーマンスクリティカルなアルゴリズムは何ですか？ポイントのLispは変更されません。つまり、挿入と削除を実行する必要はありません。このセットでターゲットxq、yqポイントの最近傍を見つけたいだけです。

編集1：すべてに感謝します！Stephan202が正しく推測したように、私はこれを繰り返し行いたいと思います。関数のように。リストは必ずしもソートされているわけではありません（実際、どのようにソートできるかわかりません。2列のaとyの主キーを持つテーブルのように？それが役立つ場合は、リストをソートします）。

一度リストに基づいてデータ構造を構築し、次にこの生成されたデータ構造を関数で使用します（このプロセス自体が関連している場合）。

ジェイコブありがとう。KDツリーのデータ構造が答えになるのに適しているようです（そして、そうだと思います。関連する結果が得られたら更新します）。

編集2：この問題は「最近傍」と呼ばれていることがわかりました。

編集3：最初のタイトルは「アルゴリズムを求めて（空間クエリと空間インデックス用）（最近傍）」でした。新しいタイトルを選択しました：「ベストパフォーマンス-最近傍を解くための重要なアルゴリズム」。初期データに対して挿入および削除操作を実行したくなく、それらから新しいポイント（挿入されない）に最も近いデータだけが必要なため、（現在）KDツリーで作業することにしました。ありがとうございます！

C＃でいくつかのオープンソースのR-Tree実装を見つけましたが、ドキュメントも開発者以外の誰かによって使用されている兆候もありません。

SQL2008を使用せずに.NETで空間クエリを実装することを検討しています。最初の要件は、（BTreeスタイルの）空間インデックスを作成してクエリできるようにすることです。

SQL 2008には、タイプ用の.NETライブラリが付属していますが、空間インデックスにはSQLを使用する必要があります。

空間データ（OSまたは商用）に.NETライブラリを使用した人はいますか？私はNetTopologySuiteを見ていますが、静かに見え、死んだライブラリは必要ありません。

lucene の空間検索コンポーネント (lucene 3.0) を使用した経験のある人はいますか?

非常に単純な例を試しましたが、検索で何も返されませんでした。すべてのコードについては以下を参照してください

ヘルプ/コメントは大歓迎です。

2D空間インデックスの質問：

ノードに絶対座標も絶対スケールも含まれていない、本質的に無限*の四分木であるデータ構造を何と呼びますか？各ノードの座標系は単位正方形（0,0）-（1,1 ）、そしてトップレベルのノードが完全に固定されていないのはどれですか？

もちろん、これは四分木ですが、どのような種類の四分木ですか？（一般的な名前はありますか？文献で名前が付けられ定義されている数十種類の四分木を見てきましたが、この特定のものは見ていません。）

シーンをレンダリングするために、いくつかの開始ノード（必ずしもルートである必要はありません）、ピクセル単位のサイズ、および画面上の位置が与えられます。次に、現在の変換行列を使用して座標をスケーリングすることにより、ノード内のすべてのオブジェクトを描画します。これをスタックにプッシュし、ツリーを下るときに半分にします。したがって、ノードの絶対座標は、レンダリング中の一時的な作業変数を介してのみ使用可能であり、データ構造自体には含まれていません。

ノード内のオブジェクトがノードの外側（たとえば、単位正方形の外側）に移動した場合、別のノードに再割り当てするためにそのオブジェクトを親に渡します。オブジェクトが断片化した場合（たとえば、小惑星が弾丸に当たった場合）、小さい部分は子ノードに渡されます。子ノードは、各ノード内の単位正方形の正規化を維持するために座標を適切にスケーリングする必要があります。

ここでの空間インデックスで使用される従来のクアッドツリー実装との主な違いは、オブジェクトの座標が、オブジェクトが含まれているノードの座標系に常に相対的であるということです。この相対主義は、位置だけでなくスケールにも当てはまります。

*絶対座標がない場合は無限大。倍精度浮動小数点座標でさえ、絶対測位に使用すると位置とサイズに制限があります。

ほとんどの平均的な PHP Web 開発者と同様に、私は MySql を RDBMS として使用しています。MySql (他の RDBMS も同様) は SPATIAL INDEX 機能を提供しますが、私はそれをよく理解していません。私はそれをグーグルで検索しましたが、それについての私の悪い知識を明確にするための明確な実世界の例は見つかりませんでした.

SPATIAL INDEXとは何か、いつ使用する必要があるのか​​ 、誰かが少し説明してもらえますか?

ID とタイムスタンプを持つデータを含む大きなテーブル (> 50m 行) があります。

...上に複数列のインデックスがあり(id, timestamp)ます。

タイムスタンプが2つの日付の間にある特定のIDを持つすべての行を選択するには、テーブルをクエリする必要があります。これは現在使用しています:

これは現在、ハイエンドマシン (2x 3Ghz デュアルコア Xeons、HT、16GB RAM、RAID 0 の 2x 1TB ドライブ) で 2 分以上かかります。

空間インデックスの使用を推奨するこのヒントを見つけましたが、その例は IP アドレス用です。ただし、速度の向上 (436 秒から 3 秒) は印象的です。

これをタイムスタンプで使用するにはどうすればよいですか?

Rectangles のインデックスを提供するデータ構造を探しています。四角形が画面上を移動するため、挿入アルゴリズムをできるだけ高速にする必要があります (マウスで四角形を新しい位置にドラッグすることを考えてください)。

R-Tree、R+Tree、kD-Tree、Quad-Tree、B-Tree を調べましたが、私の理解では挿入は通常遅いです。リストされたデータ構造のいずれかについて誰かが私が間違っていることを証明できるように、サブリニア時間の複雑さで挿入することを好みます。

ポイント(x、y)にある長方形、または長方形(x、y、幅、高さ)と交差する長方形について、データ構造を照会できるはずです。

編集: 挿入を非常に速くしたい理由は、画面上で四角形を移動することを考えると、それらを削除してから再挿入する必要があるためです。

ありがとう！

私は、扱っているデータ セットに対して適切な SQL Server 2008 空間インデックスのセットアップを選択しようとしています。

データセットは、地球全体の等高線を表すポリゴンです。テーブルには 106,000 行あり、ポリゴンはジオメトリ フィールドに格納されています。

私が抱えている問題は、多くのポリゴンが地球の大部分をカバーしていることです。これにより、プライマリ フィルターで多くの行を除外する空間インデックスを取得することが非常に難しくなっているようです。たとえば、次のクエリを見てください。

これは、テーブル内の 2 つのポリゴンのみと交差する領域をクエリしています。選択した空間インデックス設定の組み合わせに関係なく、その Filter() は常に約 60,000 行を返します。

もちろん、Filter() を STIntersects() に置き換えると、必要な 2 つのポリゴンだけが返されますが、当然、はるかに時間がかかります (Filter() は 6 秒、STIntersects() は 12 秒)。

60,000 行で改善される可能性が高い空間インデックスのセットアップがあるかどうか、または私のデータセットが SQL Server の空間インデックスとうまく一致しないかどうかについて、誰かヒントを教えてもらえますか?

より詳しい情報：

示唆されたように、世界中の 4x4 グリッドを使用して、ポリゴンを分割しました。QGIS でそれを行う方法が見つからなかったので、それを行うための独自のクエリを作成しました。最初に 16 個のバウンディング ボックスを定義しました。最初のボックスは次のようになりました。

次に、各境界ボックスを使用して、そのボックスと交差するポリゴンを選択して切り捨てました。

明らかに、4x4 グリッドの 16 個のバウンディング ボックスすべてに対してこれを行いました。最終結果は、約 107,000 行の新しいテーブルを作成したことです (これは、実際には多くの巨大なポリゴンがないことを確認しています)。

オブジェクトごとに 1024 セルの空間インデックスを追加し、レベルごとのセルには低、低、低、低を追加しました。

ただし、非常に奇妙なことに、分割されたポリゴンを含むこの新しいテーブルは、古いテーブルと同じように機能します。上記の .Filter を実行しても、最大60,000 行が返されます。私はこれをまったく理解していません。明らかに、空間インデックスが実際にどのように機能するかを理解していません。

逆説的に、.Filter() はまだ 60,000 行を返しますが、パフォーマンスは向上しています。.Filter() は 6 秒ではなく約 2 秒かかり、.STIntersects() は 12 秒ではなく 6 秒かかるようになりました。

ここで要求されているのは、インデックスの SQL の例です。

覚えていますが、オブジェクトごとにグリッドとセルのさまざまな設定を試しましたが、毎回同じ結果が得られました。

sp_help_spatial_geometry_index を実行した結果は次のとおりです。これは、単一のポリゴンが地球の 1/16 以上を占めていない私の分割データセットです。

Base_Table_Rows 215138 Bounding_Box_xmin -90 Bounding_Box_ymin -180 Bounding_Box_xmax 90 Bounding_Box_ymax 180 Grid_Size_Level_1 64 Grid_Size_Level_2 64 Grid_Size_Level_3 64 Grid_Size_Level_4 64 Cells_Per_Object 16 Total_Primary_Index_Rows 378650 Total_Primary_Index_Pages 1129 Average_Number_Of_Index_Rows_Per_Base_Row 1 Total_Number_Of_ObjectCells_In_Level0_For_QuerySample 1 Total_Number_Of_ObjectCells_In_Level0_In_Index 60956 Total_Number_Of_ObjectCells_In_Level1_In_Index 361 Total_Number_Of_ObjectCells_In_Level2_In_Index 2935 Total_Number_Of_ObjectCells_In_Level3_In_Index 32420 Total_Number_Of_ObjectCells_In_Level4_In_Index 281978 Total_Number_Of_Interior_ObjectCells_In_Level2_In_Index 1 Total_Number_Of_Interior_ObjectCells_In_Level3_In_Index 49 Total_Number_Of_Interior_ObjectCells_In_Level4_In_Index4236 Total_Number_Of_Intersecting_ObjectCells_In_Level1_In_Index 29 Total_Number_Of_Intersecting_ObjectCells_In_Level2_In_Index 1294 Total_Number_Of_Intersecting_ObjectCells_In_Level3_In_Index 29680 Total_Number_Of_Intersecting_ObjectCells_In_Level4_In_Index 251517 Total_Number_Of_Border_ObjectCells_In_Level0_For_QuerySample 1 Total_Number_Of_Border_ObjectCells_In_Level0_In_Index 60956 Total_Number_Of_Border_ObjectCells_In_Level1_In_Index 332 Total_Number_Of_Border_ObjectCells_In_Level2_In_Index 1640 Total_Number_Of_Border_ObjectCells_In_Level3_In_Index 2691 Total_Number_Of_Border_ObjectCells_In_Level4_In_Index 26225 Interior_To_Total_Cells_Normalized_To_Leaf_Grid_Percentage 0.004852925 Intersecting_To_Total_Cells_Normalized_To_Leaf_Grid_Percentage 0.288147586 Border_To_Total_Cells_Normalized_To_Leaf_Grid_Percentage 99.70699949 Average_Cells_Per_Object_Normalized_To_Leaf_Grid 405.7282349 Average_Objects_PerLeaf_GridCell 0.002464704 Number_Of_SRIDs_Found 1 Width_Of_Cell_In_Level1 2.8125 Width_Of_Cell_In_Level2 0.043945313 Width_Of_Cell_In_Level3 0.000686646 Width_Of_Cell_In_Level4 1.07E-05 Height_Of_Cell_In_Level1 5.625 Height_Of_Cell_In_Level2 0.087890625 Height_Of_Cell_In_Level3 0.001373291 Height_Of_Cell_In_Level4 2.15E-05 Area_Of_Cell_In_Level1 1012.5 Area_Of_Cell_In_Level2 15.8203125 Area_Of_Cell_In_Level3 0.247192383 Area_Of_Cell_In_Level4 0.003862381 CellArea_To_BoundingBoxArea_Percentage_In_Level1 1.5625 CellArea_To_BoundingBoxArea_Percentage_In_Level2 0.024414063 CellArea_To_BoundingBoxArea_Percentage_In_Level3 0.00038147 CellArea_To_BoundingBoxArea_Percentage_In_Level4 5.96E-06 Number_Of_Rows_Selected_By_Primary_Filter 60956 Number_Of_Rows_Selected_By_Internal_Filter 0 Number_Of_Times_Secondary_Filter_Is_Called 60956 Number_Of_Rows_Output 2 Percentage_Of_Rows_NotSelected_By_Primary_Filter 71.66655821 Percentage_Of_Primary_Filter_Rows_Selected_By_Internal_Filter 0 Internal_Filter_Efficiency 0 Primary_Filter_Efficiency 0.003281055

「Base_Table_Rows 215138」はあまり意味がありません。テーブルには215,000ではなく107,000行があります

レンダリングすると、データセットは次のようになります: _{(ソース: norman.cx )}

さらなる研究:

このデータを使用したプライマリ フィルターのパフォーマンスの悪さに、私は引き続き戸惑っています。そこで、データがどのように分割されるかを正確に確認するためのテストを行いました。元の分割されていない機能を使用して、テーブルに「セル」列を追加しました。次に、16 のクエリを実行して、フィーチャが 4x4 グリッド内でいくつのセルにまたがっているかをカウントしました。そこで、各セルに対して次のようなクエリを実行しました。

次に、表の「セル」列を見ると、データ セット全体で、4x4 グリッド内の複数のセルと交差するフィーチャは 672 個しかありません。では、まったく文字通り、幅 200 マイルの小さな四角形を参照するクエリに対して、プライマリ フィルターが 60,000 個のフィーチャを返すことができるでしょうか。

この時点で、これらの機能に対する SQL Server のパフォーマンスよりも優れた独自のインデックス作成スキームを作成できるようです。