1

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

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

在数据库中使用时，geohashed 数据的结构有两个优点。首先，由 geohash 索引的数据将在连续切片中包含给定矩形区域的所有点（切片数量取决于所需的精度和 geohash“断层线”的存在）。这在单个索引查询比多索引查询更容易或更快的数据库系统中特别有用。其次，这种索引结构可用于快速而肮脏的邻近搜索——最近的点通常在最近的地理哈希中。

因此，例如要找到“sj8101b085”的邻居，我只是计划通过执行以下操作来搜索哈希：

SELECT * FROM Users WHERE Geohash LIKE 'sj8101b085%'

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

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

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

4

2 回答 2

3

geohash 是一个位串，其中偶数位表示经度，奇数位表示纬度。例如，经度表示的每一位选择可行区域的一半。初始可行区域为[-180, 180]，如果经度的第一位为0，则下一个可行区域为[-180, 0]，如果为1，则为[0, 180]。前两位一起选择赤道上方或下方的一半地球以及本初子午线左侧或右侧的一半地球。您可以将其视为“矩形区域”，正如您在 Wikipedia 链接中所称的那样。前四位加在一起，选择北半球或南半球的一半，以及东半球或西半球的一半。等等。

链接中显示的 geohash ezs42 是基数 32，因此每个字符代表 geohash 的 5 位。示例哈希为 5 个字符的含义是，geohash 为 25 位，其中 13 位用于经度，12 位用于纬度。这意味着经度被分成了 13 倍，而纬度被分成了 12 倍，geohash 选择了 12 个纬度范围中的一个和 13 个经度范围中的一个。从哈希末尾删除的每个字符都会从 geohash 中删除 5 位；这相当于经度 3 格和纬度 2 格，反之亦然。否则，它会将您的纵向范围增加 8 倍，将您的纬度范围增加 4 倍，反之亦然。

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

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

于 2015-07-10T16:15:47.757 回答
0 
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);
}
于 2020-10-02T11:02:25.177 回答