GitHub user neggert opened a pull request: https://github.com/apache/spark/pull/15018
[SPARK-17455][MLlib] Improve PAVA implementation in IsotonicRegression ## What changes were proposed in this pull request? New implementation of the Pool Adjacent Violators Algorithm (PAVA) in mllib.IsotonicRegression. The previous implementation could have factorial complexity in the worst case. This implementation, which closely follows those in scikit-learn and the R `iso` package, runs in quadratic time in the worst case. ## How was this patch tested? Existing unit tests in both `mllib` and `ml` passed before and after this patch. Scaling properties were tested by running the `poolAdjacentViolators` method in [scala-benchmarking-template](https://github.com/sirthias/scala-benchmarking-template) with the input generated by ```{scala} val x = (1 to length).toArray.map(_.toDouble) val y = x.reverse.zipWithIndex.map{ case (yi, i) => if (i % 2 == 1) yi - 1.5 else yi} val w = Array.fill(length)(1d) val input: Array[(Double, Double, Double)] = (y zip x zip w) map{ case ((y, x), w) => (y, x, w)} ``` Before this patch: | Input Length | Time (us) | | ------------:| ---------:| | 100 | 1.35 | | 200 | 3.14 | | 400 | 116.10 | | 800 | 2134225.90| After this patch: | Input Length | Time (us) | | ------------:| ---------:| | 100 | 1.25 | | 200 | 2.53 | | 400 | 5.86 | | 800 | 10.55 | Benchmarking was also performed with randomly-generated y values, with similar results. You can merge this pull request into a Git repository by running: $ git pull https://github.com/neggert/spark SPARK-17455-isoreg-algo Alternatively you can review and apply these changes as the patch at: https://github.com/apache/spark/pull/15018.patch To close this pull request, make a commit to your master/trunk branch with (at least) the following in the commit message: This closes #15018 ---- commit 5608ae1f4c9089dd3a299eef14af59bed6c96192 Author: z001qdp <nicholas.egg...@target.com> Date: 2016-09-08T21:43:24Z New PAVA implementation ---- --- If your project is set up for it, you can reply to this email and have your reply appear on GitHub as well. If your project does not have this feature enabled and wishes so, or if the feature is enabled but not working, please contact infrastructure at infrastruct...@apache.org or file a JIRA ticket with INFRA. --- --------------------------------------------------------------------- To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org For additional commands, e-mail: reviews-h...@spark.apache.org