在地理空间索引上划分查询

Question

我正在寻找使用类似geohash的索引来存储地理空间信息，可能使用Hilbert曲线。我的问题是关于如何最好地在这样的索引上分割区域查询。

This文章举例说明了如何将一个区域查询拆分为多个查询以避免查询显示较差的区域（请参阅this图像）。如果你想用一个单一的查询来搜索圆形区域，就像使用正常的geohash一样使用Z曲线，你将不得不查询整个左下象限，它只有我们关注的区域的一小部分。

在这种情况下，将搜索分为几个查询会更好，但是我一直无法找到有关如何最好地执行此操作的任何信息。是否有算法将这样的范围查询分割成覆盖原始区域的较小范围？

Answer 1

一旦您确定了涵盖您的查询边界的哈希前缀，您就可以开始将该前缀分割为组成前缀，并在保留之前测试它们是否与查询边界相交。例如，假设您已将前缀0100标识为覆盖您的查询区域。前缀0100包括前缀01000和01001，而前缀01000包括前缀010000和010001，前缀01001包括前缀010010和010011等。当您将前缀重写为较大前缀的集合（对应于更小的区域），您可以过滤掉那些不与查询边界相交的前缀。你必须在某个时候停止分裂过程;每次分割迭代可能使前缀集的大小增加一倍。例如，您可以创建一个最大前缀集合大小，在此点您声明对您的过滤满意;当然，还有其他的指标可以用来找到一个停止点。作为最后一步，您可以重新组合“相邻”前缀，以减少您正在执行的搜索次数。例如，如果您留下前缀01000和01001，则可以将这些前缀合并为0100以避免搜索01000，然后搜索01001（假设搜索过程的开销超过顺序读取的优势） 。您将需要一个计算哈希前缀边界框的例程，以便测试与查询边界的交集。这将取决于您使用的散列方案。