srowen commented on a change in pull request #26415: [SPARK-18409][ML] LSH
approxNearestNeighbors should use approxQuantile instead of sort
URL: https://github.com/apache/spark/pull/26415#discussion_r347156855
##########
File path: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala
##########
@@ -137,14 +139,23 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
val hashDistUDF = udf((x: Seq[Vector]) => hashDistance(x, keyHash),
DataTypes.DoubleType)
val hashDistCol = hashDistUDF(col($(outputCol)))
- // Compute threshold to get exact k elements.
- // TODO: SPARK-18409: Use approxQuantile to get the threshold
- val modelDatasetSortedByHash =
modelDataset.sort(hashDistCol).limit(numNearestNeighbors)
- val thresholdDataset = modelDatasetSortedByHash.select(max(hashDistCol))
- val hashThreshold = thresholdDataset.take(1).head.getDouble(0)
-
- // Filter the dataset where the hash value is less than the threshold.
- modelDataset.filter(hashDistCol <= hashThreshold)
+ val modelDatasetWithDist = modelDataset.withColumn(distCol, hashDistCol)
+ var filtered: DataFrame = null
+ var requestedNum = numNearestNeighbors
+ do {
+ requestedNum *= 2
+ if (requestedNum > modelDataset.count()) {
+ requestedNum = modelDataset.count().toInt
+ }
+ var quantile = requestedNum.toDouble / modelDataset.count()
+ var hashThreshold = modelDatasetWithDist.stat
+ .approxQuantile(distCol, Array(quantile), 0.001)
+
+ // Filter the dataset where the hash value is less than the threshold.
+ filtered = modelDatasetWithDist.filter(hashDistCol <= hashThreshold(0))
Review comment:
To do it in one pass, we need (p - err) * N >= M, where M is the number of
nearest neighbors. We'd chose the quantile p to be some multiple k of the
desired quantile M/N. I think that works out to needing k >= err * N / M + 1.
So maybe it's a matter of fixing some err that gets a good speedup, like 0.1,
and then just picking quantile p = err + M / N. Makes sense, really: you have
to increase the desired quantile by err.
How about something like that as a one-pass solution? It just also means
checking that if p > 1 then just fall back to sort + take.
----------------------------------------------------------------
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:
[email protected]
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
