The paper describes an online one-pass algorithm for which this is not true: as you get each input value you accept or reject it. So you only need O(1) space to store the number of values you've seen, the number remaining, and the number you still need to accept.

The number of values you've seen could be "only" an exabyte, which is a problem.

You're storing the number of values you've seen:

    So far, I've seen 172 values.

You're not storing the values themselves. If the number of values you've processed is too large to fit in memory... you probably had to spend a long, long time processing those values. It's not a relevant objection.