ジオスペースインデックスへのクエリの分割

Question

ジオハッシュのようなインデックスを使用して、おそらくヒルベルト曲線を使用してジオスペース情報を格納する方法を検討しています。私の質問は、そのようなインデックス上で領域クエリを分割する最良の方法に関するものです。

Thisの記事では、地域のクエリが複数のクエリに分割され、地域性が低い範囲を回避する方法を示しています（thisイメージ参照）。通常のgeohashのようなZカーブを使用して単一のクエリで円形領域を検索する場合は、関係する領域のわずかな部分だけを持つ左下象限全体をクエリする必要があります。

この場合、検索をいくつかのクエリに分割する方が良いでしょうが、これを行うにはどのように最善の方法を見つけることができませんでした。このような範囲クエリを元の領域をカバーするより小さな範囲に分割するアルゴリズムはありますか？

Answer 1

クエリの範囲をカバーするハッシュプレフィックスを特定したら、そのプレフィックスを構成プレフィックスに分割し、各プレフィックスを保持する前にそれぞれがクエリの境界と交差するかどうかをテストすることができます。たとえば、クエリ領域をカバーする接頭辞0100を指定したとします。接頭辞0100は接頭辞01000と01001で構成され、接頭辞01000は接頭辞010000と010001で構成され、接頭辞01001は接頭辞010010と010011などから構成されます。接頭辞を大きな接頭辞の集合として書き直しています小さな領域）では、クエリ境界と交差しない接頭辞を除外することができます。ある時点で分割プロセスを停止する必要があります。分割を繰り返すたびに接頭辞コレクションのサイズが倍増する可能性があります。たとえば、フィルタに満足していることを宣言した時点で、プレフィックス集合の最大サイズを作成することができます。もちろん、停止点を見つけるために使用できる他の指標もあります。最後のステップとして、実行している検索の数を減らすために、 "隣接する"プレフィックスを再結合することができます。たとえば、接頭辞01000と01001が残っている場合は、これらを組み合わせて0100を検索し、続いて01001を検索しないようにすることができます（検索プロセスに順次読み取りを超えたオーバーヘッドがあるという前提のもとでの利点） 。クエリ境界との交差をテストするために、ハッシュ接頭辞のバウンディングボックスを計算するルーチンが必要です。これは、使用するハッシュスキームに依存します。