zhengruifeng edited a comment on issue #26948: [SPARK-30120][ML] LSH approxNearestNeighbors should use BoundedPriorityQueue when numNearestNeighbors is small URL: https://github.com/apache/spark/pull/26948#issuecomment-568335734 @srowen @huaxingao I rethinked this more, and I found another solution: 1, current impl need a threshold, we no longer need `BoundedPriorityQueue`. Current impl compute count and quantile on two pass, we can just compute them together on only one pass. So the advantage that `BoundedPriorityQueue` do not need an extra pass does not exist, `approxQuantile` is enough, but we need to use `QuantileSummaries` directly; 2, still for top-K when nn is small (maybe < 1000 at first?). Why not using `BoundedPriorityQueue` to directly collect the top-K **rows (now distCol for a threshold)**? 3, for the final `modelSubsetWithDistCol.sort(distCol).limit(numNearestNeighbors)`. when nn is small, using `BoundedPriorityQueue` to avoid global sort.
---------------------------------------------------------------- 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]
