BigQuery/SQL 中的一维推土机距离

Question

设 P 和 Q 是整数上的两个有限概率分布，支持介于 0 和某个大整数 N 之间。P 和 Q 之间的一维 earth mover's distance 是您转换所需的最小成本P 变成 Q，考虑到它花费 r*|n-m|到 "move" 与整数 n 关联的概率 r 到另一个整数 m.

有一个简单的 algorithm 可以计算这个。在伪代码中：

previous = 0
sum = 0
for i from 0 to N:
    previous = P(i) - Q(i) + previous
    sum = sum + abs(previous)         // abs = absolute value
return sum

现在，假设您有两个表，每个表都包含一个概率分布。 n 列包含整数，p 列包含相应的概率。这些表是正确的（所有概率都在 0 和 1 之间，它们的总和是我想计算 BigQuery 中这两个表之间的推土机距离（标准 SQL）。

可能吗？我觉得有人需要使用分析函数，但我对它们没有太多经验，所以我不知道如何到达那里。
如果 N（最大整数）很大，但我的表不是，怎么办？我们能否调整解决方案以避免对每个整数 i 进行计算？

Answer 1

希望我完全理解你的问题。这似乎是您要找的东西：

WITH Aggr AS (
  SELECT rp.n AS n, SUM(rp.p - rq.p)
  OVER(ORDER BY rp.n ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS emd
  FROM P rp
  LEFT JOIN Q rq
  ON rp.n = rq.n
) SELECT SUM(ABS(a.emd)) AS total_emd
FROM Aggr a;

WRT 问题 #2，请注意，我们只扫描表中的实际内容，而不考虑 N，假设 one-to-one P 中的每个 n 与 Q 中的 n 匹配。

Answer 2

我改编了 Michael 的回答来解决它的问题，这是我最终得到的解决方案。假设整数存储在列 i 中，概率存储在列 p 中。首先，我连接了两个表，然后我使用 window 计算所有 i 的 EMD(i)，然后我对所有绝对值求和。

WITH
joined_table AS (
  SELECT
    IFNULL(table1.i, table2.i) AS i,
    IFNULL(table1.p, 0) AS p,
    IFNULL(table2.p, 0) AS q,
  FROM table1
  OUTER JOIN table2
  ON table1.i = table2.i
),
aggr AS (
  SELECT
    (SUM(p-q) OVER win) * (i - (LAG(i,1) OVER win)) AS emd
  FROM joined_table
  WINDOW win AS (
    ORDER BY i
    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  )
)
SELECT SUM(ABS(emd)) AS total_emd
FROM aggr

BigQuery/SQL 中的一维推土机距离

One-dimensional earth mover's distance in BigQuery/SQL

sql

google-bigquery

distance

probability-distribution