How to make representative sample set from a large overall dataset? What are the statistical techniques to create a sample set, which is representative of the entire population (with a known confidence level)? 
Also,


*

*How to validate, if the sample fits the overall dataset?

*Is it possible, without parsing the entire dataset (which could be billions of records)?

 A: If you don't wish to parse the entire data set then you probably can't use stratified sampling, so I'd suggest taking a large simple random sample. By taking a random sample, you ensure that the sample will, on average, be representative of the entire dataset, and standard statistical measures of precision such as standard errors and confidence intervals will tell you how far off the population values your sample estimates are likely to be, so there's no real need to validate that a sample is representative of the population unless you have some concerns that is was truly sampled at random.
How large a simple random sample? Well, the larger the sample, the more precise your estimates will be. As you already have the data, conventional sample size calculations aren't really applicable -- you may as well use as much of your dataset as is practical for computing. Unless you're planning to do some complex analyses that will make computation time an issue, a simple approach would be to make the simple random sample as large as can be analysed on your PC without leading to paging or other memory issues. One rule of thumb to limit the size of your dataset to no more than half your computer's RAM so as to have space to manipulate it and leave space for the OS and maybe a couple of other smaller applications (such as an editor and a web browser). Another limitation is that 32-bit Windows operating systems won't allow the address space for any single application to be larger than $2^{31}$ bytes = 2.1GB, so if you're using 32-bit Windows, 1GB may be a reasonable limit on the size of a dataset.
It's then a matter of some simple arithmetic to calculate how many observations you can sample given how many variables you have for each observation and how many bytes each variable takes up.
A: On your second question first, you might ask, "how was the data entered?" If you think that the data was entered in a relatively arbitrary fashion (i.e., independent of any observable or unobservable characteristics of your observations that might influence your ultimate analysis using the data), then you might consider the first 5 million, say, or however many you're comfortable working with, as representative of the full sample and select randomly from this group to create a sample that you can work with.
To compare two empirical distributions, you can use qq-plots and the two-sample Kolmogorov–Smirnov non-parametric test for differences in distributions (see, e.g., here: http://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test). In this case, you would test the distribution of each variable in your sample against the distribution of that variable in your "full" data set (again, it could be just 5 million observations from your full sample). The KS test can suffer from low power (i.e., it's hard to reject the null hypothesis of no difference between the groups), but, with that many observations, you should be okay.
