SAMPLING TO ESTIMATE THE NUMBER OF DUPLICATES IN A DATABASE

The problem of estimating the number of duplicate records in a database by sampling is explored. Sampling is done with probability of selection proportional to size, with size being defined as the number of records equivalent to a given record. The cost of sampling this way forces the sample sizes to be small. Two estimators are given for with- and without-replacement sampling. A sample-based estimator of the variance of the with-replacement estimator is available but not for the without-replacement estimator and thus is determined by computer simulation. Because of the size of the population and the many populations possible, efficient simulation software was constructed and is described. Simulations show that in our application, both estimators are accurate for small samples and the estimates are nearly identical. This is supported by mathematical analysis.