hadoop - 使用Hadoop工具集匹配地理位置

Question

我有两个数据集，比如说 checkin 和POI，我必须根据地理坐标将它们加入:比如说，如果在POI附近看到用户位于N km半径内，我需要将它们加入(换句话说，我想要收集每个POI附近的所有用户以进行进一步的操作)。但是我对这种地理匹配有问题...

最初，我看到两个不同的机会:
1)实现LSH(位置敏感的哈希)-看起来确实很复杂，性能也会受到影响
2)将所有 map 分割成区域(2D矩阵)，然后计算距离签到或POI N公里以内的区域数量-然后发出所有区域-结果必须进行重复数据删除-因此，不确定其是否有效完全是算法

任何最佳做法？

Answer 1

有趣的问题。

我认为您已经考虑过幼稚的暴力方法，并且发现它太耗时了。在蛮力方法中，您需要计算每个n POI与每个m checkin 点之间的距离，从而导致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入门介绍。