How to make an effective sampling from a database of text documents?

Question

Problem: I want to know methods to perform an effective sampling from a database. The size of the database is about 250K text documents and in this case each text document is related to some majors (Electrical Engineering, Medicine and so on). So far I have seen some simple techniques like Simple random sample and Stratified sampling; however, I don't think it's a good idea to apply them for the following reasons:

• In the case of simple random sample, for instance, there are a few documents in the database that talk about majors like Naval Engineering or Arts. Therefore I think they are less likely to be sampled with this method but I would like to have some samples of every major as possible.

• In the case of stratified sampling, most of the documents talk about more than one major so I cannot divide the database in subgroups because they will not be mutually exclusive, at least for the case in which each major is a subgroup.

Finally, I cannot use the whole database due to expensive computational cost processing. So I would really appreciate any suggestions on other sampling methods. Thanks for any help in advance.

Answer 1

If you considered stratified sampling, I take it you have a variable in your database that indicates for each text file which major(s) it belongs to ? Then I suggest you use two-stage sampling and then use the "weight share method" so you don't have to worry about your clusters not being mutually exclusive.

The weight share method gives an unbiased estimator when sampled units "could have been drawn from several subsamples", which in your case means "drawn from several clusters". All you need is to be able to track down the number of texts belonging to each combination of majors. If you find units in your sample corresponding to more than one major, you can compute their "shared" weights using the number of links between each clusters. See for instance :

• Deville, J.-C., and Lavallée, P. (2006). Indirect sampling: The foundations of the generalized weight share method. Survey Methodology, Vol. 32, 2, 165-176.
• Lavallée, P., and Caron, P. (2001). Estimation using the generalised weight share methods: The case of record linkage. Survey Methodology, Vol. 27, 2, 155-169.

Also, there are probably a lot of majors in your database. If you choose to make one cluster per major, you'll probably end up with some clusters holding very few responding units, which will make variance estimation very difficult. I suggest you assign each major a score (based on what you want to measure, say on a 1-3 or 1-5 scale), and use it to create your clusters.

Finally, don't forget to ouse post-stratification methods (or calibration), as I'm sure you can easily compute totals for a lot of variables from your database.

EDIT : Stratified sampling is also a form of two-stage sampling, so all I wrote about "multistage sampling" and "clusters" is also valid for "stratified sampling" and "strata".

Answer 2

There is an algorithm for simple random sampling (without replacement, equal probabilities), but it can of course be adapted to stratified sampling by applying it to each strata. Suppose you want a sample of size $n$ from a database with $N$ individuals (texts in your case), where we do not need to know $N$ in advance, we only assume that we can query the database to give us all the items, in some order.

The algorithm is simple and simple to implement (and it ought to be an option in many database systems?). Step by step:

• select the $n$ first individuals as a current sample.
• each subsequent individual is rejected with probability $1-n/t$ where $t$ is the index number of the individual seen.
• if selected, the new individual replaces one of the members of the current sample, chosen with equal probability.
• continue until the database is exhausted

This algorithm is given on page 80 of Brian Ripley's "Stochastic Simulation", Wiley, where also a proof is given. It deserves to be better known.