Geohash：使用libgeohash查找邻居

Question

在我的应用程序中，我将所有用户的Geohash存储在一个表中，并希望找到使用这些Geohashes的用户的邻居。

按照信息，我收集到的有关地理散列上Wiki：

如果在数据库中，geohashed数据的结构有两个 优势。首先，由geohash索引的数据将具有在连续切片中给定矩形区域的 的所有点（切片的数量 取决于所需的精度以及存在地理散列“故障 行”）。这在数据库系统中特别有用，其中单个索引上的查询 比多索引 查询更容易或更快。其次，这个索引结构可以用于 快速和肮脏的邻近搜索 - 最接近的点通常在最接近的地理杂乱之间。

因此对于例如找到“sj8101b085”的邻居，我曾计划在做搜索的哈希值：

SELECT * FROM Users WHERE Geohash LIKE 'sj8101b085%' 

由一个即“sj8101b08％”，“sj8101b0％”，降低哈希长度一个发射相同的查询，然后直到我得到所需的邻居数量。我的印象是，这是我需要做的。

但后来我发现这个C库libgeohash在同一篇文章的底部提到。该库有一个叫做GEOHASH_get_adjacent的函数，它给了我们给定散列的相邻哈希值。 geohash字符串表示地球上的矩形区域。这个函数返回表示相邻矩形的地理杂乱。这意味着我必须在递归中运行这个函数（邻居，然后是邻居的邻居等），直到我得到所需的邻居数量。

现在我很困惑我该如何编写我的搜索算法？使用第一种方法或使用第二种？

Answer 1

geohash是一个位串，偶数位代表经度，奇数位代表纬度。例如，经度表示的每一位选择可行区域的一半。初始可行区域为[-180,180]，如果经度的第一位为0，则下一个可行区域为[-180,0]，如果为1，则变为[0,180]。前两位合在一起，选择赤道上方或下方的地球一半，以及地球的一半，位于主子午线的左侧或右侧。您可以将其视为“矩形区域”，因为它在维基百科链接中被调用。前四位合起来选择北半球或南半球的一半，以及东半球或西半球的一半。等等。

链接中显示的geohash，ezs42是基数32，因此每个字符表示geohash的5位。示例散列的含义是5个字符，是地理散列是25位，其中13个是经度，其中12个是纬度。这意味着经度被分为13次，而纬度被分成12次，而地球哈罗选择12个纬度范围中的一个和13个纵向范围中的一个。从散列末尾删除的每个字符都会消除地理散列中的5位;这相当于经度为3格，纬度为2格，反之亦然。换句话说，它将你的纵向范围增加8倍，你的纬度范围增加4倍，反之亦然。查询该geohash会给出相应“矩形”区域内的所有点。

我不熟悉libgeohash;然而，从您的描述中，它听起来好像给了它一个geohash，并且它以给定的粒度表示相邻“矩形”区域的geohashes集合。据推测，如果你使用它来寻找最近的邻居，你需要跟踪你已经访问过的地图集和你没有的地图集，而且你必须反复询问邻居，直到你找到你的点正在寻找。从视觉上来说，这看起来像是从你最初的“矩形”的大小的“矩形”的初始geohash扇出。您需要小心，不要简单地考虑在邻近区域中找到的第一个点，因为另一个邻近区域可能有更接近查询点的点;也就是说，在搜索离您的查询点最近的k之前，您需要先考虑所有邻居中的点（例如，这意味着您需要向所有8个邻居请求和查询点在邻居方法的第二次迭代中寻找你的最近的k之前，原始“矩形”的邻居）。

考虑到libgeohash邻居方法，如果你的原始“矩形”很小（比如英寸），并且你的点很稀疏，那么可能需要很长时间直到你覆盖足够的地球煽动技术直到你找到你的观点。另一方面，使用前缀方法，可能是因为您的点数足够密集，以至于将范围扩大4倍和8倍，可以考虑大量的点。无论哪种情况，如果您正在寻找k个最近邻居，您仍然需要测试所有得到的距离点，以选择距离它们最近的k个点。最终，您的选择将取决于您的数据;但是，我建议从前缀方法开始，因为它比相邻的“矩形”区域方法简单得多。