用星火[``cartesian()‘问题创建一个邻域矩阵
我是一个星火初学者，我面临着以下问题:我有一个项目集合(假设它们是笛卡尔坐标或2D点)，并且我希望得到它们的近邻元素。判断一项是否接近另一项取决于一个函数(假设我们想要欧氏距离小于给定值的所有点)。
当然，得到一个点的邻居是微不足道的，我已经做到了。只要filter的项目和仅此而已。我不能做的是为集合中的所有点获取它们，而我不知道如何有效地做到这一点。
我在这里写了一个我想从一个小数据集中得到的结果的例子，以更清楚地说明我的需求：
sourceData = [ (0,1) , (1,1), (0,0), (50,10), (51,11) ]
result = [
(0,1) => [(1,1), (0,0)],
(1,1) => [(0,1), (0,0)],
(0,0) => [(0,1), (1,1)],
(50,10) => [(51,11)],
(51,11) => [(50,10)]
]你知道如何有效地做到这一点吗？
到目前为止，我已经尝试过了：
return sourceData.cartesian(sourceData)
.filter(new PairNeighborFilter<T>())
.groupByKey();使用
public class PairNeighborFilter<T extends DbScanPoint> implements Function<Tuple2<T, T>, Boolean> {
/**
*
*/
private static final long serialVersionUID = 1L;
public static double eps;
@Override
public Boolean call(Tuple2<T, T> v1) throws Exception {
return v1._1().distanceTo(v1._2()) <= eps && !v1._1().equals(v1._2());
}
}但我相信这样做是一种非常低效的方法。此外，稍后我需要计算每个键的元素，这只能对所有元素进行迭代和计数，这是性能的另一个耻辱。我希望有一个JavaRDD类作为JavaPairRDD的值，而不是Iterable的值，这可能吗？
谢谢。
回答 1
Stack Overflow用户
发布于 2016-02-25 18:13:57
为了有效地找到邻居，您可能希望避免执行一个完整的笛卡尔积，因为它是一个O(n^2)操作。另一种方法是使用局部敏感散列来识别一组较小的候选点对，然后计算候选对之间的精确距离。(这是一种“近似的”最近邻方法，因为对于任何特定点，某些真正的最近邻居可能不会像所讨论的点那样散列到同一桶中。)
有可用于此的几个ANN/LSH星火包。
https://stackoverflow.com/questions/28727823
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号