1. 5
  1.  

  2. 1

    I’m sure Vitter’s “skipping” variant of reservoir sampling has been reinvented many times. Another application of the “skipping” trick is Jump Consistent Hashing.