apache/incubator-spark — pull request #430 by bgawalt (2014-01-14 22:15:55+00:00)
Title: Empirical cumulative density function

This pull request adds a pair of new transformation methods to the RDD class in order to calculate the empirical cumulative distribution function value for each member of an RDD, according to a user-provided `Ordering`. This is computed in three steps:

1. Produce a sorted version of the RDD. Implemented as its own new method (for better testability, and since it's a useful addition on its own), `RDD[T].sort(ord: Ordering[T], numPartitions: Int)`, using the `RangePartitioner` approach cribbed from `sortByKey`. Specifically: sort the elements in the _reverse_ order `ord` prescribes.

2. In the driver, collect the size of each partition. This partition-sizes collection is broadcast to the RDD.

3. In each partition, count how many elements are "bigger" than you in an `ord` sense living in the other partitions, as well as the total count of all RDD members. Step through the reverse-ordered `Iterator`s of each partition, incrementing this `numBigger` count with each element seen, emitting either the element and a score of `(numTotal - numBigger)/numTotal))`, or, in case of tie, the score emitted for the preceding element.

Some aspects to consider in particular:

1. The partition-sizes collection is actually implemented as a Map from [an element pulled from the partition] `T` to a [partition size] `Long`. It would be O(num. partitions) faster to use a map from partition ID to partition size, _but_, I was afraid of committing `ecdf` to a permanent contract on how the partition IDs are assigned in a `RangePartition`ed RDD.

2. I've exposed `ecdf` through the Java API, but didn't move `sort` along with it. I figured it'd be more useful to decide if the feature is worth merging at all, then set up a separate issue to port the `sort(ord)` method later if desired.