奇怪的性能问题 Spark LSH MinHash approxSimilarityJoin

Question

我正在使用 Apache Spark ML LSH 的 approxSimilarityJoin 方法加入 2 个数据集，但我看到了一些奇怪的行为。

在（内部）连接之后，数据集有点偏斜，但是每次完成一个或多个任务都需要花费过多的时间。

正如您所看到的，每个任务的中位数是 6 毫秒（我在较小的源数据集上运行它进行测试），但 1 个任务需要 10 分钟。它几乎不使用任何 CPU 周期，它实际上连接了数据，但是速度太慢了。下一个最慢的任务在 14 秒内运行，有 4 倍多的记录并且实际上溢出到磁盘。

如果你看

连接本身是根据 minhash 规范和 udf 计算匹配对之间的 jaccard 距离的 pos & hashValue (minhash) 上的两个数据集之间的内部连接。

分解哈希表：

modelDataset.select(
      struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))

杰卡德距离函数：

modelDataset.select(
      struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))

连接处理过的数据集：

 override protected[ml] def keyDistance(x: Vector, y: Vector): Double = {
    val xSet = x.toSparse.indices.toSet
    val ySet = y.toSparse.indices.toSet
    val intersectionSize = xSet.intersect(ySet).size.toDouble
    val unionSize = xSet.size + ySet.size - intersectionSize
    assert(unionSize > 0, "The union of two input sets must have at least 1 elements")
    1 - intersectionSize / unionSize
  }

我尝试了缓存、重新分区甚至启用的组合spark.speculation，但都无济于事。

数据由必须匹配的带状疱疹地址文本组成： 53536, Evansville, WI=>53, 35, 36, ev, va, an, ns, vi, il, ll, le, wi 将与城市或邮编有拼写错误的记录有一段短距离。

这给出了非常准确的结果，但可能是连接偏斜的原因。

我的问题是：

• 什么可能导致这种差异？（一项任务需要很长时间，即使它的记录较少）
• 如何在不丢失准确性的情况下防止 minhash 中的这种偏差？
• 有没有更好的方法来大规模地做到这一点？（我不能 Jaro-Winkler / levenshtein 将数百万条记录与位置数据集中的所有记录进行比较）

Answer 1

可能有点晚了，但无论如何我都会在这里发布我的答案以帮助其他人。我最近在匹配拼写错误的公司名称时遇到了类似的问题（All executors dead MinHash LSH PySpark approxSimilarityJoin self-join on EMR cluster）。有人帮助我建议采用 NGrams 来减少数据偏差。这对我帮助很大。您也可以尝试使用例如 3-grams 或 4-grams。

\n

我不\xe2\x80\x99不知道数据有多脏，但你可以尝试使用状态。它已经大大减少了可能匹配的数量。

\n

真正帮助我提高匹配准确性的是通过在每个组件上运行标签传播算法来对连接组件（由 MinHashLSH 生成的连接匹配组）进行后处理。这还允许您增加 N（NGram），从而减轻数据倾斜的问题，不太approxSimilarityJoin严格地设置杰卡德距离参数，并使用标签传播进行后处理。

\n

最后，我目前正在研究使用skipgrams来匹配它。我发现在某些情况下它效果更好并且在一定程度上减少了数据偏差。

\n