zhengruifeng commented on a change in pull request #26858: [SPARK-30120][ML] Use BoundedPriorityQueue for small dataset in LSH approxNearestNeighbors URL: https://github.com/apache/spark/pull/26858#discussion_r358620083
########## File path: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ########## @@ -138,21 +139,31 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]] // Limit the use of hashDist since it's controversial val hashDistUDF = udf((x: Seq[Vector]) => hashDistance(x, keyHash), DataTypes.DoubleType) val hashDistCol = hashDistUDF(col($(outputCol))) - - // Compute threshold to get around k elements. - // To guarantee to have enough neighbors in one pass, we need (p - err) * N >= M - // so we pick quantile p = M / N + err - // M: the number of nearest neighbors; N: the number of elements in dataset - val relativeError = 0.05 - val approxQuantile = numNearestNeighbors.toDouble / count + relativeError val modelDatasetWithDist = modelDataset.withColumn(distCol, hashDistCol) - if (approxQuantile >= 1) { - modelDatasetWithDist + // for a small dataset, use BoundedPriorityQueue + if (count < 1000) { + val queue = new BoundedPriorityQueue[Double](count.toInt)(Ordering[Double]) Review comment: I wrongly thought that the `approxNearestNeighbors` only return an approximate threshold, then we can use top-k to obtain an exact threshold. Since the `approxNearestNeighbors` already gaurantee an enough threshold which had already taken the relative error into account, so **I guess we no longer need a top-k solution.** A `BoundedPriorityQueue` only maintains the topK entries, so it should be much smaller than a `QuantileSummaries`, however since there is only one column to process, so there should be no performance gain. ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org For additional commands, e-mail: reviews-h...@spark.apache.org