I used to work on a hospital database, back before the internet. It happened a few times that we were asked for a random sample of records. It was quite commo

I used to work on a hospital database, back before the internet. It happened a few times that we were asked for a random sample of records. It was quite common to want to recalculate the rehabilitation rates and other stats. This was a problem, as patient records filled several tapes and, being the youngster, I had to sit loading tapes for hours. Because our data set was bigger than memory, we had trouble deciding what to sample. We'd read everything in, filtering the records, and recording just their offsets. Then we'd pick some number, then re-read all the tapes to fetch the actual records. Naive and tedious. Luckily the IT manager knew all about reservoir sampling, and explained it to us. We made a little Turbo Pascal program that ran over the data files each night before they were archived to tape and kept a large (but small enough to fit on one machine) reservoir! Every time we were asked after that for a random sample after that we just handed out the reservoir. The care managers, who thought they were still causing us to sit for hours shuffling tapes, were terribly grateful at the quick turnarounds. We never did let them in on our secret. These days of course hospital records fit in RAM. Not the same kind of problems.