cockroachdb/cockroach — pull request #44 by tobstar87 (2014-09-10 07:17:59+00:00)
Title: add weighted reservoir sampling (AE-S)

Implemented algorithm A-Res from http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf, offering a reservoir sampling algorithm with the chance of each element being in the final sample being proportional to the (positive) weight assigned to each element.
If need arises we will fairly easily be able to implement A-ExpJ using this (but I don't think we'll ever need it) to save some random numbers.
The careful reviewer will observe that really I would have wanted a priority queue instead of an abstract heap (to get "peek") but in this version the exposition is clearer and the performance hit isn't more than a slightly worse constant depending on the reservoir size.
A-Res will be used to generate the split key when it is needed, taking the size of key-value pairs as their weight. Other metrics are possible, allowing for a range of interesting split key criteria.