如何避免交叉连接以查找Spark数据帧中每两行之间的成对距离

Question

我有一个火花数据框，有三列，指示原子的位置，即位置X，Y

df = atomsDF.withColumn("id", F.monotonically_increasing_id())
windowSpec = W.orderBy("id")
df = df.withColumn("id", F.row_number().over(windowSpec))
df_1 = df.select(*(F.col(col).alias("{}_1".format(col)) for col in df.columns))
df_3 = df_1.crossJoin(df).where("id_1 != id")

df_3 = df_3.withColumn(
        "Distance",
        F.sqrt(
            F.pow(df_3["Position_X_1"] - df_3["Position_X"], F.lit(2))
            + F.pow(df_3["Position_Y_1"] - df_3["Position_Y"], F.lit(2))
            + F.pow(df_3["Position_Z_1"] - df_3["Position_Z"], F.lit(2))
        )
    )

我的数据框如下所示：

Position_X|Position_Y|Position_Z|
+----------+----------+----------+
|    27.545|     6.743|    12.111|
|    27.708|     7.543|    13.332|
|    27.640|     9.039|    12.970|
|    26.991|     9.793|    13.693|
|    29.016|     7.166|    14.106|
|    29.286|     8.104|    15.273|
|    28.977|     5.725|    14.603|
|    28.267|     9.456|    11.844|
|    28.290|    10.849|    11.372|
|    26.869|    11.393|    11.161|
+----------+----------+----------+

现在，我如何避免交叉连接，因为交叉连接后，行数呈指数增长？例如，对于交叉连接后有3000行的数据集，总行数增长到3000*2999=8997000，这非常耗时。还有其他有效的方法来计算每两行之间的成对距离吗？




Answer 1

你说你需要找到每两个原子之间的距离。因此，由于结果大小为N^2，因此运行时间按定义是二次的。你可以对它进行一些优化，但它仍然是二次的。

只有当你实际上不需要找到每两个原子之间的N^2距离，而只需要根据一些标准找到对时，你才能优化它。

例如，人们通常需要找到比某个阈值距离更近的对，因为R树提供了更好的可伸缩性。在Spark中，可能更容易将原子分裂成大小等于阈值距离的立方体网格，然后只需要在相同或相邻立方体中的原子和原子之间交叉连接。