The current quantiles implementation has served us well, but may need to be redone. It was, I believe, the result of a quick whiteboard session rather proper research of existing algorithms.

It has some accuracy concerns (see #731) and is also fairly slow when operating on many many partitions (around 1 minute on the nyctaxi data).

People have suggested t-digest in the past. This has all of the operations that we need. It is a bit overkill but also widely implemented and trusted.