Как избежать перекрестного соединения, чтобы найти попарное расстояние между каждыми двумя строками в кадре данных Spark - PullRequest
Новая
       30

Как избежать перекрестного соединения, чтобы найти попарное расстояние между каждыми двумя строками в кадре данных Spark

0 голосов
/ 03 мая 2019

У меня есть фрейм данных искры с 3 столбцами, которые указывают позиции атомов. I-e Position X, Y & Z. Теперь, чтобы найти расстояние между каждыми 2 атомами, для которых мне нужно применить формулу расстояния. Формула расстояния d= sqrt((x2−x1)^2+(y2−y1)^2+(z2-z1)^2). Для меньшего набора данных мне было рекомендовано перекрестное соединение, но для большого набора данных это очень неэффективно и отнимает много времени. В настоящее время я использую следующий фрагмент кода. 

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))
        )
    )

Мой Dataframe выглядит следующим образом: 

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, что делает его очень трудоемким. Любой другой Эффективный способ найти попарное расстояние между каждыми двумя рядами?

1 Ответ

1 голос
/ 03 мая 2019

Вы говорите, что вам нужно найти расстояние между каждыми 2 атомами.Для этого, поскольку размер результата равен N ^ 2, время выполнения по определению является квадратичным.Вы можете оптимизировать его несколько, но он все равно будет квадратичным.

Вы можете оптимизировать его, только если вам на самом деле не нужно находить N ^ 2 расстояний между каждыми 2 атомами, а нужно находить только пары на основенекоторые критерии.

Например, обычно нужно найти пары, которые ближе, чем пороговое расстояние - для этого R-деревья обеспечивают гораздо лучшую масштабируемость.В Spark может быть проще разделить атомы на сетку кубов размером, равным пороговому расстоянию, тогда вам нужно только перекрестное соединение между атомом и атомами в одном и том же или соседних кубах.

...