Geohash：使用 libgeohash 查找邻居

Question

在我的应用程序中，我将所有用户的 Geohash 存储在 table 中，并希望使用这些 Geohash 查找用户的邻居。

根据我在 Wiki 上收集到的有关 Geohash 的信息：

When used in a database, the structure of geohashed data has two advantages. First, data indexed by geohash will have all points for a given rectangular area in contiguous slices (the number of slices depends on the precision required and the presence of geohash "fault lines"). This is especially useful in database systems where queries on a single index are much easier or faster than multiple-index queries. Second, this index structure can be used for a quick-and-dirty proximity search - the closest points are often among the closest geohashes.

例如找到 "sj8101b085" 的邻居，我只是计划通过以下方式搜索哈希：

SELECT * FROM Users WHERE Geohash LIKE 'sj8101b085%'

然后通过一个一个地减少散列长度来触发相同的查询，即 "sj8101b08%"、"sj8101b0%" 等等，直到我得到所需数量的邻居。我的印象是这就是我需要做的。

但后来我在同一篇文章的底部找到了这个 C 库 libgeohash。该库有一个名为 GEOHASH_get_adjacent 的函数，它为我们提供给定散列的相邻散列。 geohash 字符串表示地球上的一个矩形区域。这个函数 returns geohashes 表示相邻的矩形。这意味着我在递归中得到运行这个函数（邻居，然后是邻居的邻居等等），直到我得到所需数量的邻居。

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

Answer 1

geohash 是一个位串，偶数位代表经度，奇数位代表纬度。每一位表示经度，例如selects的半个可行区域。初始可行区为[-180, 180]，如果经度第一位为0，则下一个可行区为[-180, 0]，为1则为[0, 180]。前两位合起来，select 地球在赤道以上或以下的一半，以及地球在本初子午线左侧或右侧的一半。您可以将其视为 "rectangular area"，因为它在您的维基百科中被称为 link。前四位合起来，select北半球或南半球的一半，以及东半球或西半球的一半。等等。

您的 link 中显示的 geohash ezs42 是 base 32，因此每个字符代表 geohash 的 5 位。示例哈希为 5 个字符的含义是，geohash 为 25 位，其中 13 位用于经度，12 位用于纬度。也就是说经度13分，纬度12分，geohash select 都是纬度十二分之一，经度十三个分之一。从散列末尾删除的每个字符都会从 geohash 中删除 5 位；这相当于经度的 3 个格和纬度的 2 个格，反之亦然。换句话说，它会将您的经度范围增加 8 倍，将您的纬度范围增加 4 倍，反之亦然。查询该 geohash 会给出落在相应 "rectangular" 区域内的所有点。

我不熟悉libgeohash；但是，根据您的描述，听起来好像您给它一个 geohash，它会返回一组 geohashes，这些 geohashes 以输入隐含的粒度表示相邻的 "rectangular" 区域。据推测，如果你用它来寻找最近的邻居，你将需要跟踪你访问过的和你没有访问过的那些 geohashes，你将不得不反复询问邻居，直到你找到你想要的点正在寻找。从视觉上看，这看起来像是从 "rectangles" 的初始 geohash 散开的，它是原始 "rectangle" 的大小。您需要注意不要简单地考虑您在一个邻近区域中找到的第一个点，因为另一个邻近区域可能有一个点更接近您的查询点；也就是说，在搜索最接近您的查询点的 k 之前，您需要考虑来自 all 个邻居的点（这意味着，例如，您需要询问和在寻找你的 k 最近的邻居方法的第二次迭代之前，从原始 "rectangle" 的所有 8 个邻居的邻居查询点。

考虑到 libgeohash neighbor 方法，如果您的原始 "rectangle" 很小（例如，一英寸一英寸），并且您的点足够稀疏，则可能需要大量时间才能覆盖足够多的点通过这种散开的技术来接地，直到找到你的点。另一方面，使用前缀方法时，您的点可能足够密集，以至于将范围增加 4 倍和 8 倍会产生大量要考虑的点。在任何一种情况下，如果您正在寻找 k 个最近的邻居，您仍然需要测试所有结果点到最近的 select k 个点的距离。最后，您的选择将取决于您的数据；但是，我建议从前缀方法开始，因为它比相邻 "rectangular" 区域方法要简单得多。

Answer 2

public Set<String> getMoreNeighbours(int surroundRange, String originHash){
    int matrixSize = nthOddNumber(surroundRange / 5);
    Set<String> locationSet = new HashSet<>();
    locationSet.add(originHash);
    List<String> tempNbHash = new ArrayList<>();
    for(int i=0; i < matrixSize / 2; i++) {
        if(tempNbHash.isEmpty()) {
        Map<String, Boolean> memo = new HashMap<>();
            Set<String> collection = new HashSet<>();
            locationSet.forEach(loc -> {
                if (!memo.containsKey(loc)) {
                    Collection<? extends CharSequence> neighbors = GeoHashUtils.neighbors(loc);
                    neighbors.forEach(nb -> collection.add(nb.toString()));
                }
                memo.put(loc, true);
            });
            locationSet.addAll(collection);
            tempNbHash.addAll(collection);
        } else {
            Map<String, Boolean> memo = new HashMap<>();
            Set<String> collection = new HashSet<>();
            tempNbHash.forEach(loc -> {
                if (!memo.containsKey(loc)) {
                    Collection<? extends CharSequence> neighbors = GeoHashUtils.neighbors(loc);
                    neighbors.forEach(nb -> collection.add(nb.toString()));
                }
                memo.put(loc, true);
            });
            locationSet.addAll(collection);
            tempNbHash.clear();
            tempNbHash.addAll(collection);
        }
    }
    return locationSet;
}

public int nthOddNumber(int n){
    return (2 * n - 1);
}

Geohash：使用 libgeohash 查找邻居

Geohash: Using libgeohash to find neighbors

algorithm

geolocation

geocoding

geo

geohashing