<p>You can try the A-ES algorithm from <a href="http://arxiv.org/pdf/1012.0256.pdf" rel="nofollow noreferrer">this paper of S. Efraimidis</a>. It's quite simple to code and very efficient.</p>

<p>Hope this helps,</p>

<p>Benoit</p>
Is there an algorithm for weighted reservoir sampling?
<p>Is there an algorithm for how to perform reservoir sampling when the points in the data stream have associated weights?</p>