Imagine that you want to assess the compressibility of a large document very fast. You could randomly pick a subsequence, try to compress it. This can serve as a prediction for the overall compressibility of the document. But how big should your sample be?

We have come up with the following strategy:

  1. Pick an arbitrary (small) sample size. Measure the compressibility.
  2. Next, double the sample size and measure the compressibility again. If there is little change (say less than 10%), then conclude that you have reliably determined the compressibility of the document. If not, double the sample size again, and so on.

We are quite certain that this is not a new strategy, and we are wondering whether it is related to some well-known strategy used by statisticians.

("Compression" here is just an example. Basically, we are interested in a metric that has no known nice mathematical properties, so that it is not possible to determine analytically what could be a good sample size. We have no choice but to fall back on such heuristics.)


This has been called 'Progressive Sampling', e.g. http://citeseerx.ist.psu.edu/viewdoc/download?doi=

  • $\begingroup$ The reference given by CDX is: Foster Provost, David Jensen, and Tim Oates. 1999. Efficient progressive sampling. In Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '99). ACM, New York, NY, USA, 23-32. $\endgroup$ – Daniel Lemire Jul 12 '11 at 13:07

Your Answer

