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

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.

• With quota sampling you could ensure that you choose x documents on each major (if that many exist). – rolando2 Mar 11 '15 at 1:16
• @rolando2 I just read about quota sampling and I think it won't be so helpful because it is pretty similar to the stratified sampling and is non-probabilistic. Also the method requires mutually exclusive groups, if I set each group to be a major then the problem is that the documents can belong to more than one group (as I said a document can talk about many majors). Thus breaking that requirement. Am I right? – Kevin Bello Mar 11 '15 at 3:56
• Exactly what do you know about each document in advance of sampling? Do you know all the majors it is related to? For example, you say that there are a few documents about Naval Engineering? How do you know this? – Steve Samuels Mar 15 '15 at 22:10
• @SteveSamuels Yes, each document has an attribute containing all the majors related to it. I used a regex pattern to find them. – Kevin Bello Mar 16 '15 at 15:21

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".

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.