Need a probabilistic approach to determine if a data-set A includes all the elements of data-set B My job is to identify if the two given datasets are same. This is to be done on computers using some programming language (C++).
Since the data could be huge, I don't want to read all the elements of one set and compare with the other one. I guess, it is okay, if one could tell me that there is, for example, 95% probability that two data sets are same or that one is subset of the other. I want some mathematical/probabilistic/statistical method of comparison where I don't have to perform a brute force method.
 A: If you can afford going through each data set once, then you can compare the two scores based on some rule. In particular, you can compare the two histograms. This does not involve matching numbers in each data set, which is good.
If you would like to do even less, you can sample $N$ points in each data set. Then you can compare the two samples using the two-sample Kolmogorov-Smirnov test. You choose $N$ in such a manner so that

*

*when the data sets are same and you say so, you are correct 95% of the time,

*when the data sets are different and you say so, you are correct 95% of the time.

Please note: we are talking about probabilistic testing. Not digital signatures. So each direction can only be achieved up to small variations in the two data sets.
A: If exact comparison is needed then histograms or other distribution approximations won't help. I was thinking a little bit about that since it's a nice problem to solve and I have some solutions which I will group based on how much you afford to spend in terms of data reading and memory usage.
If you can afford to read both data sets once, then there are a variety of solutions available. You can build a hash set where you collect hash values from one set and later on you can iterate on the second set. The hash collections will be very large perhaps you have to use disk.
If you need to avoid large collection space in memory you can use it instead a data structure like Bloom filters. It will save you a lot of space required for storing the set, the price being that it is a probabilistic structure. When it says the element is not contained, then you can be sure it's true. If it says it is contained in the set, then it might be wrong with a probability of error decided by the Bloom filter parameters. There are also very memory-tight Bloom filter variations, so you can improve on that.
I suppose that in order to avoid at all reading the whole data you need to devise a sampling procedure of some sort. This looks tricky in more aspects. One of the aspects is data access itself. If random access is available or data is streamed. Random sampling is possible if random acess is available, but for streamed data the sampling scheme depends a lot on how data is stored.
For streamed data it is probably hard to avoid to read the whole data, or at least a large chunk of it. However, you can take a sample from data using some sort of hash slicing (for example taking all the instances which have hash(object)%32==0). Since the hash function is uniform than you know that objects from the sample is representative. At the same time one sample from each set would produce instances for which the comparison makes sense. We know that one instance from a set for each if $hash(o_1)\%z \neq hash(o_2)\%z$ then $o1 \neq o2$. This kind of sampling is very efficient in obtaining two samples which are representative for the large populations and are comparable, but reading most of the data cannot be avoided.
If random access is possible then one can avoid reading all the data at the price that the two samples are represenattives but contains elements which are hardly comparable if the sample is not large enough.
Even in the last case some statistical test can be devised. Consider having two sets $S_1$ and $S_2$. Let's suppose that both sets have dimension $n$. If we take two samples $s_1$ and $s_2$ of size $k$, then we can see that the probability that an element from $s_1$ to be in the sample $s_2$ is $\frac{k}{n}$ (Bernoulli). The number of elements which are in both sets is distributed as $Binomial (\frac{k}{n}, k)$.
A very simple way to devise a test is to consider the null hypothesis $H_0$ to be that the sets are equal, the alterative hypothesis being the complement. For large values of $k\frac{k}{n}$ you can use normal approximation and as a consequence a t test. Notice that the sample size should obey a rule like $k\frac{k}{n} \ge 100$ (or some other number, 1000 maybe, larger is better). The means that if you have a million elements than you cannot use a sample size of 1000, you need at least $k=10000$.
Another interesting test which can be done would be a likelihood ratio test. The point of the likelihood ration test is to compare the ration between the likelihood under null hypothesis agains the supremum of the likelihood on all other possible values, which is the maximum likelihood estimator. To construct one you do not need to use normal approximation, it is much handy to work directly with binomial. However you should enrich the expressivity in the following way. Let's denote with $p$ the proportion of elements which both population have in common. For equal populations we should have then $p=1$, otherwise the $p$ should be less than one, but greater oer equal with zero. The binomial will look like:
$$P(x_i|p,k,n) = C_k^i \left(p\frac{k}{n}\right)^{x_i} \left(1 - p\frac{k}{n}\right)^{k - x_i}$$
Likelihood under null hypoithesis $H_0$ is
$$L(X|p=1,k,n,m) = \prod_{i=1}^m C_k^i \left(\frac{k}{n}\right)^{x_i} \left(1 - \frac{k}{n}\right)^{k - x_i}$$
and for the alternate hypothesis is
$$L(X|p=p_{ML},k,n,m) = \prod_{i=1}^m C_k^i \left(p_{ML}\frac{k}{n}\right)^{x_i} \left(1 - p_{ML}\frac{k}{n}\right)^{k - x_i}$$
The $p_{ML}$ estimate is the maximum likelihood estimator of $p$ under considered data $X$. It can be easily found by deriving the likelihood as a function of p, equaling with zero and solving for $p$. You should obtain something like:
$$p_{ML} = \frac{n}{k^2}\frac{1}{m}\sum_{i=1}^m x_i = \frac{n}{k^2} \bar{x}$$
where we have $\bar{x}$ the mean, $m$ number of times we repeat the sampling procedure (we can do it more if we want to gain better results, but it can be one if you want to work with a simple pair of samples).
Now use
$$\lambda(p) = -2(l(p_0 = 1) - l(p_{ML}))$$ and according with Wilk's Teorem it should be distributed as $\chi_1^2$. The Neyman-Pearson_lemma goes into the direction that which test is the most powerfull and this is what you need in order to get most of it, since having random sampling makes the situation a lot worser than for hash slicing sampling I presented before.
I hope that it is clear eanough and the ideas were helpful. I did not found a solution in terms of package ready to be used since it is rather a niche problem, but it is not hard to implement both tests and use simulations to see how it works. From my simulations I used 10 million population size and 100_000 as sample size. The first test works well if the population have common elements less that 0.95. The second test looks well even if there are differences of one percentage of populations and even less.
A final note: take into consideration that I used as null hypothesis the statement that sets are equal. Because of that the first consequence is that you cannot prove that the sets are equal, but if they are different. Something like "I found or not a significant difference in samples, and as a consequence in population." If I fail to prove a difference we should be content with assuming they are equal. Proving beyond that means comparing all the elements from populations.
