使用Hadoop工具集匹配地形点

Question

我有两个数据集，假设是签到和POI，我必须基于地理坐标连接它们:假设用户在POI附近半径N公里的范围内，我需要连接它们(换句话说，我希望收集每个POI附近的所有用户以进行进一步操作)。但我对地理位置匹配有个问题...

最初，我看到了两个不同的机会: 1)实施LSH (位置敏感哈希)-看起来非常复杂，性能也可能会受到影响2)将所有地图分割成区域(2D矩阵)，然后计算出与签到或POI之间的N km距离内有多少区域-然后发出所有区域-结果是必须应用一些重复数据消除-因此，根本不确定它是否有效

有什么最佳实践吗？

Answer 1

有趣的问题。

我假设您已经考虑过简单的暴力方法，并发现它对于您的目的来说太耗时了。在暴力方法中，您计算每个n POI和每个m签入之间的距离，从而导致O(n*m)的时间复杂性。

我能想到的最简单的启发式方法也适用于Spark，那就是通过将数据集元素分组到桶中来减少对一个数据集的全线性扫描。如下所示：

case class Position(x: Double, y: Double)
val checkins: RDD[Position] = ???
val radius = 10
val checkinBuckets = checkins.groupBy(pos => (pos.x/radius).toInt)

人们可以只搜索对应的、下一个和前一个桶，而不是完全线性扫描。如果需要，可以通过对存储桶进行分组来创建第二个级别，以进一步加快查找速度。此外，还应该注意pos.x/radius、gps distance calculation等的正确舍入等细节。

当然，你可以像@huitseeker所说的那样，在various approaches中寻找最近的邻居搜索问题。此外，this paper有一个很好的介绍NNS的介绍。