# Data Sampling while preserving the underlying distribution

I have a large 10-15 dimensional data set with close to 10 million points. I want to test some algorithms over a chunk of this data. But I don't want the character of this data to be lost by selecting a random chunk (say first 100 thousand points). I want to get a sample of this data such that if in some part of space the data points are distributed densely as compared to some other part of the space, then this character should be preserved in the sample also. Are there any open source tools for doing this or any algorithm that can quickly be implemented ? The exact distribution of this data (as a mathematical expression) is not known.

• Why not more than one chunks, and compare the results of the algorithm? – Alecos Papadopoulos Jan 13 '15 at 15:48
• Are all dimensions equally important? If not, can you roughly rank them in importance? – Steve Samuels Jan 28 '15 at 23:54

Use reservoir sampling. It's really simple, and it will give you a random sample in one pass over the data set, without needing random access.

1. Fix your sample size. Say 10000.
2. Take the first 10000.
3. Initialize i to 10000.
4. For each following sample, increase i. If random(1...i)==1, replace a random one of your existing samples, otherwise discard the new sample.

The chances of an object surviving in the reservoir until the end is the same as being chosen by random sampling without replacement.

Vitter, Jeffrey S. (1 March 1985). "Random sampling with a reservoir". ACM Transactions on Mathematical Software 11 (1): 37–57. doi:10.1145/3147.3165.

http://en.wikipedia.org/wiki/Reservoir_sampling

I want to get a sample of this data such that if in some part of space the data points are distributed densely as compared to some other part of the space, then this character should be preserved in the sample also.

If I understand correctly, you want the probability distribution of the sample you pick from your large dataset to be similar (to approximate) the distribution of the large dataset. But this is guaranteed if you select the 100K points at random. Just pick sufficiently many rows between 1 and 10 million, without replacement (without picking the same row twice). This is usually referred to as simple random sample.