You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by GitBox <gi...@apache.org> on 2019/12/13 06:24:20 UTC
[GitHub] [spark] zhengruifeng commented on a change in pull request #26858:
[SPARK-30120][ML] Use BoundedPriorityQueue for small dataset in LSH
approxNearestNeighbors
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_r357500230
##########
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:
This place should be like:
```scala
val exactThreshold = modelDatasetWithDist
.select(distCol)
.as[Double]
.rdd
.treeAggregate(new BoundedPriorityQueue[Double](numNearestNeighbors)(Ordering[Double].reverse))(
seqOp= (q, v) => q += v,
combOp = (q1, q2) => q1 ++= q2,
depth = 2
).toArray.max
```
And this impl should have no dependency on the size of dataset.
----------------------------------------------------------------
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:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org