lipton and j. naughton presented an adaptive random sampling algorithm for database querying which is applicable to any query for which answers to the query can be partitioned into disjoint subsets. unlike most sampling estimation algorithms—which statically determine the number of samples needed—their algorithm decides the number of samples based on the sizes of the samples, and tends to keep the running time constant (as opposed to linear in the number of samples).