使用geohash进行邻近搜索？

#1 楼

绝对可以。而且速度可能很快。 （密集的计算位也可以分配）

有几种方法，但是我一直在使用的一种方法是使用基于整数的有序哈希表的有序列表，并找到所有最近的特定geohash分辨率（分辨率近似于您的distance标准）的邻近geohash范围，然后查询这些geohash范围以获取附近点的列表。我为此使用redis和nodejs（即javascript）。 Redis超级快，可以非常快速地检索有序范围，但是它不能执行SQL数据库可以执行的很多索引查询操作。

方法概述如下：https：// github.com/yinqiwen/ardb/wiki/Spatial-Index

但是要点是（释义链接）：


您存储了所有geoshashed点以有序集合（即redis中的zset）中所需的最佳分辨率（如果可以访问，则通常为最大64位整数，如果使用javascript，则为52位整数）。如今，大多数geohash库都内置了geohash整数函数，您需要使用这些函数而不是更常见的base32 geohash。
根据要在其中搜索的半径，您需要先找到一个深度/决议，将匹配您的搜索区域，并且必须小于或等于您存储的geohash位深度。链接的站点具有一个表格，该表格将geohash的位深度与其以米为单位的边界框区域相关联。
然后以较低的分辨率重新哈希原始坐标。
在较低的分辨率下还找到了8个邻居（n，ne，e，se，s，sw，w，nw）geohash区域。之所以必须执行近邻方法，是因为彼此相邻的两个坐标可能具有完全不同的地理哈希，因此您需要对搜索范围进行平均。
一旦获得所有相邻的geohash，以较低的分辨率，将步骤3中的坐标的geohash添加到列表中。
然后，您需要构建要搜索的geohash值范围，该范围涵盖这9个区域。第5步中的值是您的范围下限，如果将每个范围加1，您将获得范围的上限。因此，您应该有9个范围的数组，每个范围都有一个下限和一个上限（总共18个geohash）。这些geohash仍处于第2步中的较低分辨率。
然后，您将所有18种geohash转换为将所有geohash存储在数据库中的任何位深度/分辨率。通常，您可以通过将其移位到所需的位深度。
现在您可以对这9个范围内的点进行范围查询，所有点都将在原始点的距离范围内。不会有重叠，因此您不需要做任何交叉，只需非常快的纯范围查询即可。 （即在redis中：ZRANGEBYSCORE zsetname lowerLimit upperLimit，在此步骤中生成的9个范围内）

您可以通过以下方式（在速度方面）进一步优化：


从第6步中获取这9个范围，并找出它们之间的相互影响。通常，根据坐标的位置，您可以将9个单独的范围缩小为大约4或5。这样可以将查询时间减少一半。
一旦有了最终范围，就应保留它们以供重新使用。这些范围的计算会占用大部分处理时间，因此，如果您的原始坐标变化不大，但是您需要再次进行相同的距离查询，则应该准备好该距离，而不是每次都进行计算。
如果您使用的是redis，请尝试将查询合并到MULTI / EXEC中，以便对其进行流水线处理以获得更好的性能。
最好的部分：您可以在客户端上分配步骤2-7，而不必执行计算全部集中在一处。在将要传入数百万个请求的情况下，这大大降低了CPU负载。

如果您非常关注精度，则可以在返回的结果上使用圆距/ haversine类型的函数来进一步提高准确性。

这是使用普通的base32地理哈希和SQL查询代替redis的类似技术： http://github.com/davetroy/geohash-js

我并不是要插入自己的东西，但是我已经为nodejs＆redis编写了一个模块，这使得它真的很容易实现。如果需要，请看一下代码：https://github.com/arjunmehta/node-georedis

#2 楼

这个问题可以通过几种方式来理解。我将其解释为意味着您拥有大量点，并且打算使用任意点（以坐标对形式给出）反复探测它们，并希望获得n个与探测点最近的点，并预先固定n个点。 （原则上，如果n会变化，则可以为每个可能的n设置一个数据结构，并在每个探针的O（1）时间中选择它：这可能需要很长的设置时间，并且需要大量RAM，但是我们被告知忽略此类问题。）

建立所有点的阶n Voronoi图。这将平面划分为相连的区域，每个区域具有相同的n个邻居。这将情况简化为多边形点问题，该问题具有许多有效的解决方案。

使用Voronoi图的矢量数据结构，多边形点搜索将采用O（log（n ）） 时间。出于实际目的，只需创建图表的栅格版本，即可使O（1）的隐式系数极小。栅格中像元的值要么是（i）指向n个最近点的列表的指针，要么是（ii）该像元跨越图中两个或多个区域的指示。在（x，y）处的任意点的测试变为：

Fetch the cell value for (x,y).
If the value is a list of points, return it.
Else apply a vector point-in-polygon algorithm to (x,y).

要实现O（1）性能，栅格网格必须足够精细，以至于相对较少探针点将落在跨越多个Voronoi区域的细胞中。这总是可以实现的，而且可能会为网格存储付出巨大的代价。

#3 楼

我完全使用geohash。我之所以这样，是因为我需要使用金字塔样式的信息系统来实现邻近搜索。在这种情况下，精度为8级的地质哈希是“基础”，并且形成了精度为7级的新的地质哈希总数。 。这些总数是面积，地面覆盖物的类型等。这是做一些非常花哨的事情的非常花哨的方法。

因此，第8层地质哈希将包含以下信息： >类型：草
英亩：1.23

以及7th，6th ..等等。将包含以下信息：

草类型：123
英亩： 6502

总是以最低的精度构建的。这使我可以非常快速地进行各种有趣的统计。我还能够使用GeoJSON为每个geohash引用分配一个几何引用。

我能够编写几个函数来查找构成当前视口的最大geohash，然后使用它们来查找视口中的第二大精度。可以很容易地将其扩展到索引范围查询，无论我想要的精度如何，我都会查询最小的'86ssaaaa'和最大的'86sszzzz'。 br />

#4 楼

我建议在redis中使用GEORADIUS查询。

使用GEOADD调用将按最适合的geohash级别分片的数据推入。 ProximityHash。

ProximityHash在给定中心坐标和半径的情况下会生成一组覆盖圆形区域的地质哈希。它还有一个使用GeoRaptor的附加选项，它可以从最高级别开始迭代并直到酿造出最佳的混合物，从而在各个级别上创建最佳的地质哈希组合以表示圆。结果精度与起始geohash级别相同，但是数据大小显着减小，从而提高了速度和性能。

#5 楼

更新到2018年代，以及Geohash的一些数学基础或历史渊源：


Geohash的灵感来自于二进制数字的简单交错，也许是天真算法的优化，它交错了十进制数字，像C平方一样。
二进制交织自然产生了Z阶曲线索引策略，Geohash发明者并没有开始“寻找最佳的分形曲线”……但是，好奇的是，这种设计优化是一个更好的选择。分形曲线是可能的（！）。

使用S2几何库

S2几何方法比Geohash更好，因为它使用了球面的球形拓扑（立方体），使用了可选的投影（因此所有单元都有接近相同的形状和接近的区域），并且因为使用希尔伯特曲线进行分度比使用Z阶曲线更好：


...我们可以做得更好...从右上角到左下角四边形导致我们不得不分割一些我们可以连续的范围。 （...）我们可以完全消除使用四叉树和希尔伯特曲线进行空间索引时的任何不连续（... blog.notdot.net/2009）


现在，它是一种免费且高效的工具库，请参阅https://s2geometry.io

PS：还有（好的）非官方的简化版本，如NodeJS的s2-geometry，还有许多“游乐场”，加载项和演示，如s2。 sidewalklabs.com。