使用spark[`cartesian()`issue]创建邻居矩阵

wz3gfoph  于 2021-06-03  发布在  Hadoop
关注(0)|答案(1)|浏览(480)

我是一个spark初学者,我面临以下问题:我有一个项目集合(假设它们是笛卡尔坐标或二维点),我想得到每个项目的近元素。判断一个项目是否靠近另一个项目是由一个函数决定的(假设我们想要所有的点,其欧氏距离小于给定值)。
当然,得到一个点的邻居是微不足道的,我已经做到了。只是 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 ,这可能吗?
谢谢。

3bygqnnd

3bygqnnd1#

为了高效地找到邻居,您可能希望避免使用完全笛卡尔积,因为它是一个o(n^2)运算。另一种方法是使用对位置敏感的哈希来识别一组较小的候选点对,然后计算候选点对之间的精确距离(这是一种“近似”近邻方法,因为任何特定点的一些真正的近邻可能不会散列到与所讨论的点相同的存储桶中。)
有几个安/lshSpark包可用于此。

相关问题